Find Shortest Path Algorithm

using System;

namespace Map
{
    class Program
    {
        static public class main
        {
            public static int[,] A = new int[10000,10000];
            public static int[,] Trace = new int[10000, 10000];
            public static int n, m, Begin, End;
        }
        public static void Input()
        {
            int Start, Finish, Length;
            Console.Clear();
            Console.Write("Input number of location: ");
            main.n = int.Parse(Console.ReadLine());
            Console.Write("Input number of path: ");
            main.m = int.Parse(Console.ReadLine());
            for (int i = 1; i <= main.n; i++)
                for (int j = 1; j <= main.n; j++)
                    if (i == j) main.A[i, j] = 0;
                    else main.A[i, j] = 32000;
            for (int i=1;i<=main.m;i++)
            {
                Console.Write("Input Start-End-Length of Path: ");
                string S = Console.ReadLine();
                string[] Inp = S.Split(' ');
                Start = int.Parse(Inp[0]);
                Finish = int.Parse(Inp[1]);
                Length = int.Parse(Inp[2]);
                main.A[Start, Finish] = Length;
                main.A[Finish, Start] = Length;
            }
            Console.Write("Input Start Location: ");
            main.Begin = int.Parse(Console.ReadLine());
            Console.Write("Input Finish Location: ");
            main.End = int.Parse(Console.ReadLine());
        }
        public static void Process()
        {
            int i, j, k;
            for (i = 1; i <= main.n; i++)
                for (j = 1; j <= main.n; j++)
                    main.Trace[i, j] = j;
            for (k = 1; k <= main.n; k++)
                for (i = 1; i <= main.n; i++)
                    for (j = 1; j <= main.n; j++)
                        if (main.A[i, j] > main.A[i, k] + main.A[k, j])
                        {
                            main.A[i, j] = main.A[i, k] + main.A[k, j];
                            main.Trace[i, j] = k;
                        }

        }
        public static void Output()
        {
            if (main.A[main.Begin, main.End] == 32000) Console.WriteLine("Path Not Found!");
            else
            {
                Console.WriteLine("Length: {0}", main.A[main.Begin, main.End]);
                Console.Write("Path: {0}-", main.Begin);
                while (main.Begin!=main.End)
                {
                    Console.Write("{0}-",main.Trace[main.Begin,main.End]);
                    main.Begin = main.Trace[main.Begin, main.End];
                }
            }
        }
        static void Main(string[] args)
        {
            Input();
            Process();
            Output();
            Console.ReadLine();
        }
    }
}