C# Belman-Ford implementation
\npublic class Solution\n{\n\tpublic int NetworkDelayTime(int[][] times, int n, int k)\n\t{\n\t\t// implementation of Belman-Ford Algorithm\n\t\t// https://www.
```\npublic class Solution\n{\n\tpublic int NetworkDelayTime(int[][] times, int n, int k)\n\t{\n\t\t// implementation of Belman-Ford Algorithm\n\t\t// https://www.youtube.com/watch?v=FtN3BYH2Zes  \n\t\t// run relaxation of each vertex exactly n - 1 times\n\t\t// source vertex should have 0 cost to visit, all other vertexes should start from infinity cost\n\t\tvar costs = new Dictionary<int, double>();\n\t\tfor (int i = 1; i <= n; i++)\n\t\t\tcosts[i] = double.PositiveInfinity;\n\t\tcosts[k] = 0;\n\n\t\tint u, v, w;\n\n\t\tfor (int i = 0; i < n - 1; i++)\n\t\t{\n\t\t\tbool isRelaxed = false;\n\t\t\tfor (int t = 0; t < times.Length; t++)\n\t\t\t{\n\t\t\t\tu = times[t][0];\n\t\t\t\tv = times[t][1];\n\t\t\t\tw = times[t][2];\n\n\t\t\t\tdouble candidateCost = costs[u] + w;\n\t\t\t\tif (costs[v] > candidateCost)\n\t\t\t\t{\n\t\t\t\t\tcosts[v] = candidateCost;\n\t\t\t\t\tisRelaxed = true;\n\t\t\t\t}\n\t\t\t}\n\n\t\t\tif (!isRelaxed) \n\t\t\t\tbreak;\n\t\t}\n\n\t\tdouble maxCost = costs.Values.Max();\n\t\treturn (maxCost < double.PositiveInfinity) ? (int)maxCost : -1;\n\t}\n}\n```
[]