using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        var a = Solution.FindCheapestPrice(

            2,

            new int[][]{new int[]{1,0,5}},

            0,

            1,

            1);

        Console.WriteLine(a);

    }

}

public class Solution {

​

    private const int MaxPrice = 100000;

    private const int Inf = 100000000;

​

    public static int FindCheapestPrice(int n, int[][] flights, int src, int dst, int k) {

        var dict = new Dictionary<int,List<List<int>>>();

​

        for(int i=0;i<flights.Length;i++){

            var from = flights[i][0];

            var to = flights[i][1];

            var price = flights[i][2];

​

            List<List<int>> output;

            var currEdge = new List<int>{from, price};

​

            if(!dict.TryGetValue(to, out output)){

                dict[to] = new List<List<int>>();

            }

​

            dict[to].Add(currEdge);

            /*Console.WriteLine(

                        "Added {0} to dict[{1}]",

                        from,

                        to);*/

        }

​

        var dp = new int[k+2,n];        

        for(int i=0;i<n;i++){

            dp[0,i] = Inf;

        }

​

        dp[0,src] = 0;

​

        for(int j=1;j<k+2;j++){

            for(int i=0;i<n;i++){

                if(i == src){

                    dp[j,i] = 0;

                    continue;

                }

​

                List<List<int>> temp;

                if(!dict.TryGetValue(i, out temp))

                {

                    dp[j,i] = Inf;

                    continue;

                }

​

                var inwardNeighbours = dict[i];

                var distance = Inf;

​

                for(int ne=0;ne<inwardNeighbours.Count;ne++){

                    var from = inwardNeighbours[ne][0];

                    var price = inwardNeighbours[ne][1];

                    Console.WriteLine(

                        "From {0} to {1}, price is {2}",

                        from,

                        i,

                        price

                    );

​

                    Console.WriteLine(

                        "dp[{0}, {1}] is {2}",

                        j-1,

                        from,

                        dp[j-1, from]);

                    var newDistance = dp[j-1, from] == Inf ? Inf : dp[j-1, from] + price;

                    Console.WriteLine("NewDistance is {0}", newDistance);

                    distance = Math.Min(distance, newDistance);

                    Console.WriteLine("Distance is {0}", distance);

                }

​

                dp[j,i] = distance;                

            }

        }

​

        return dp[k+1,dst] == Inf ? -1 : dp[k+1,dst];

    }

}