using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        Console.WriteLine(12m);

        string s = "Hello my friend";

        string[] strs = s.Split(' ');

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

        {

            Console.WriteLine(strs[i]);

        }

​

        //Console.WriteLine(CountPaths(7, new int[]{0,6,7},new int[]{0,1,2},new int[]{1,2,3},new int[]{1,3,3},new int[]{6,3,3},new int[]{3,5,1},new int[]{6,5,1},new int[]{2,5,1},new int[]{0,4,5},new int[]{4,6,2}));

        //Console.WriteLine(CountPaths(12, new int[]{1,0,2348},new int[]{2,1,2852},new int[]{2,0,5200},new int[]{3,1,12480},new int[]{2,3,9628},new int[]{4,3,7367},new int[]{4,0,22195},new int[]{5,4,5668},new int[]{1,5,25515},new int[]{0,5,27863},new int[]{6,5,836},new int[]{6,0,28699},new int[]{2,6,23499},new int[]{6,3,13871},new int[]{1,6,26351},new int[]{5,7,6229},new int[]{2,7,28892},new int[]{1,7,31744},new int[]{3,7,19264},new int[]{6,7,5393},new int[]{2,8,31998},new int[]{8,7,3106},new int[]{3,8,22370},new int[]{8,4,15003},new int[]{8,6,8499},new int[]{8,5,9335},new int[]{8,9,5258},new int[]{9,2,37256},new int[]{3,9,27628},new int[]{7,9,8364},new int[]{1,9,40108},new int[]{9,5,14593},new int[]{2,10,45922},new int[]{5,10,23259},new int[]{9,10,8666},new int[]{10,0,51122},new int[]{10,3,36294},new int[]{10,4,28927},new int[]{11,4,25190},new int[]{11,9,4929},new int[]{11,8,10187},new int[]{11,6,18686},new int[]{2,11,42185},new int[]{11,3,32557},new int[]{1,11,45037}));

    }

    //  первая реализация по таймауту откосела

    public static int CountPaths(int n, params int[][] roads) 

    {

        Array.Sort(roads, (left, right) => left[0] - right[0]);

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

        {

            for(int j = 0; j < roads[i].Length; j++)

            {

                Console.Write(" - " + roads[i][j]);

            }

            Console.WriteLine("");

        }

        List<int[]>[] graph = new List<int[]>[n];

        int from;

        int to;

        int weight;

        int buf;

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

        {

            from = roads[i][0];

            to = roads[i][1];

            weight = roads[i][2];

            if (from > to)

            {

                buf = from;

                from = to;

                to = buf;

            }

            //Console.WriteLine(" - from= " + from + " to= " + to);

            if (graph[from] == null)

            {

                graph[from] = new List<int[]>();

            }

            graph[from].Add(new int[]{to, weight, 0});

        }

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

        {

            if (graph[i] == null)

            {

                continue;

            }

            for (int j = 0; j < graph[i].Count; j++)

            {

                if (graph[j] == null)

                {

                    continue;

                }

                //to = graph[start][j][0];

​

                Console.WriteLine("from= " + i + " to= " + graph[i][j][0] + " weight=" + graph[i][j][1]);

                //GoInside(graph, to, end, weight + graph[start][j][1], paths);

            }

        }

        //  проходим от каждой вершины до каждой

        //  вершину с которой просмотрели все ходы метим прошедшей и не посещаем ее

        List<int> paths = new List<int>();

        GoInside(graph, 0, n-1, 0, paths);

        paths.Sort();

        foreach(int d in paths)

        {

            Console.WriteLine(d);

        }

        return paths.FindAll((x) => x == paths[0]).Count;

    }

    private static void GoInside(List<int[]>[] graph, int start, int end, int weight, List<int> paths)

    {

        //  непосредственно обход графа с подсчетом длины пути

        int to;

        if (start == end || graph[start] == null)

        {

            if (start == end)

            {

                paths.Add(weight);

            }

            return;

        }

        for (int j = 0; j < graph[start].Count; j++)

        {

            if (graph[j] == null)

            {

                continue;

            }

            to = graph[start][j][0];

            Console.WriteLine("to= " + to);

            GoInside(graph, to, end, weight + graph[start][j][1], paths);

        }

    }

}