using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace PS1
{
    class Program
    {
        static void Main(string[] args)
        {
            #region read from file
            var filePath = @"C:\Users\Maciek\Desktop\mgr\algorytmy\PS1\in5.txt";
            var lines = File.ReadAllLines(filePath);
             //n - wierzchołki m-krawedzi
            var line = lines[0].Split(' ');
            var n = int.Parse(line[0]);
            var m = int.Parse(line[1]);
            var cords = new Dictionary<int, (int, int)>();
            var h = new Dictionary<int, int>();
            var graph = new Dictionary<int, List<int>>();
            var weights = new Dictionary<(int, int), int>();
            int padding = 0;
            for (int i = 1; i <= n; i++)
            {
                graph.Add(i, new List<int>());
            }
            if (filePath.Contains("in5"))
            {
                for (int i = 1; i <= n; i++)
                {
                    line = lines[i].Split(' ');
                    cords.Add(i, (int.Parse(line[0]), int.Parse(line[1])));
                }
                padding = n;
            }

            for (int i = 1; i <= m; i++)
            {
                line = lines[i + padding].Split(' ');

                graph[int.Parse(line[0])].Add(int.Parse(line[1]));
                graph[int.Parse(line[1])].Add(int.Parse(line[0]));
                weights.Add((int.Parse(line[0]), int.Parse(line[1])), int.Parse(line[2]));
                weights.Add((int.Parse(line[1]), int.Parse(line[0])), int.Parse(line[2]));
            }
            line = lines[m + padding + 1].Split(' ');
            var begin = int.Parse(line[0]);
            var end = int.Parse(line[1]);
            if (filePath.Contains("in5"))
            {
                var endCord = cords[end];

                for (int i = 1; i <= n; i++)
                {
                    h.Add(i, CalculateH(cords[i], endCord) );
                }
                Console.WriteLine(h[end]);


                AStar(graph, weights, n, m, begin, end, h);
            }

            #endregion read from file

            //Bfs(graph, weights, n, m, begin, end);
            Dijkstra(graph, weights, n, m, begin, end);

        }

        private static int CalculateH((int,int) node1, (int,int) node2)
        {
            var xPow = Math.Pow(node1.Item1 - node2.Item1, 2);
            var yPow = Math.Pow(node1.Item2 - node2.Item2, 2);

            return (int)Math.Sqrt(xPow + yPow);

        }

        public static void Bfs(Dictionary<int, List<int>> graph, Dictionary<(int, int), int> weights, int n, int m, int begin, int end)
        {

            var visited = new Dictionary<int,int>();
            var d = new int[n + 1];
            var previous = new int[n + 1];
            var calculated = new bool[n + 1];

            for (int i = 1; i <= n; i++)
            {
                visited[i] = int.MaxValue;
                d[i] = int.MaxValue;
                calculated[i] = false;

            }
            var queue = new Queue<int>();

            visited[begin] = 0;
            d[begin] = 0;
            queue.Enqueue(begin);

            var stopWatch = Stopwatch.StartNew();
            while (queue.Count > 0)
            {
                var v = queue.Dequeue();
                if (v == end)
                {
                    break;
                }
                foreach (var item in graph[v])
                {
                    if (!calculated [item] && d[item] > d[v] && visited[item] > visited[v] + weights[(v,item)])
                    {
                        if (visited[item] == int.MaxValue)
                        {
                            queue.Enqueue(item);
                        }
                        previous[item] = v;
                        d[item] = d[v] + 1;
                        visited[item] = visited[v] + weights[(v, item)];
                    }
                }
                calculated[v] = true;
            }
            stopWatch.Stop();
            Console.WriteLine(stopWatch.ElapsedMilliseconds + "ms");
            int current = end;
            var result = new Stack<int>();
            while (current != begin)
            {
                result.Push(current);
                current = previous[current];
            }
            result.Push(current);
            var length = result.Count();
            Console.WriteLine($"{length-2} {visited[end]}");
            for (int i = 0; i < length; i++)
            {
                Console.Write($"{result.Pop()} ");
            }

        }
        public static void Dijkstra(Dictionary<int, List<int>> graph, Dictionary<(int, int), int> weights, int n, int m, int begin, int end)
        {
            var visited = new Dictionary<int, bool>();
            var d = new int[n + 1];
            var previous = new int[n + 1];
            int v;
            for (int i = 1; i <= n; i++)
            {
                visited[i] = false;
                d[i] = int.MaxValue;
            }

            var start = new int[] { begin };
            d[begin] = 0;
            var sortedSet = new SortedSet<int>(start, new Comparer(d));

            var stopWatch = Stopwatch.StartNew();
            while (sortedSet.Count > 0)
            {
                v = sortedSet.First();
                sortedSet.Remove(v);
                visited[v] = true;

                if (v == end)
                {
                    break;
                }
                foreach (var item in graph[v])
                {
                    if (!visited[item] && d[v] + weights[(v, item)] < d[item])
                    {
                        sortedSet.Remove(item);
                        d[item] = d[v] + weights[(v, item)];
                        sortedSet.Add(item);
                        previous[item] = v;
                    }
                }
            }
            stopWatch.Stop();

            Console.WriteLine(stopWatch.ElapsedMilliseconds + "ms");

            int current = end;
            var result = new Stack<int>();
            while (current != begin)
            {
                result.Push(current);
                current = previous[current];
            }
            result.Push(current);
            var length = result.Count();
            Console.WriteLine($"{d[end]}");
            for (int i = 0; i < length; i++)
            {
                Console.Write($"{result.Pop()} ");
            }
            Console.WriteLine();
        }

        public static void AStar(Dictionary<int, List<int>> graph, Dictionary<(int, int), int> weights, int n, int m, int begin, int end, Dictionary<int,int> h)
        {
            var visited = new Dictionary<int, bool>();
            var d = new int[n + 1];
            var previous = new int[n + 1];
            int v;
            var f = new int[n + 1];
            for (int i = 1; i <= n; i++)
            {
                visited[i] = false;
                d[i] = int.MaxValue;
            }

            var start = new int[] { begin };
            d[begin] = 0;
            f[begin] = 0 + h[begin];
            var sortedSet = new SortedSet<int>(start, new Comparer(f));

            var stopWatch = Stopwatch.StartNew();
            while (sortedSet.Count > 0)
            {
                v = sortedSet.First();
                sortedSet.Remove(v);

                visited[v] = true;

                if (v == end)
                {
                    break;
                }
                foreach (var item in graph[v])
                {

                    if (!visited[item] && d[v] + weights[(v, item)] < d[item])
                    {
                        sortedSet.Remove(item);
                        d[item] = d[v] + weights[(v, item)];
                        f[item] = d[item] + h[item];
                        sortedSet.Add(item);
                        previous[item] = v;
                    }
                }
            }
            stopWatch.Stop();

            Console.WriteLine(stopWatch.ElapsedMilliseconds + "ms");

            int current = end;
            var result = new Stack<int>();
            int sum = 0;
            while (current != begin)
            {
                result.Push(current);
                sum += weights[(current, previous[current])];
                current = previous[current];

            }
            result.Push(current);
            var length = result.Count();
            Console.WriteLine($"{sum}");
            for (int i = 0; i < length; i++)
            {
                Console.Write($"{result.Pop()} ");
            }
            Console.WriteLine();
        }


    }
}
//////////////////////////////////////////////////////////////klasa do comparatora
using System;
using System.Collections.Generic;
using System.Diagnostics.CodeAnalysis;
using System.Text;

namespace PS1
{
    public class Comparer : IComparer<int>
    {
        public int[] dist { get; set; }
        public Comparer(int[] dist)
        {
            this.dist = dist;
        }
        public int Compare(int x, int y)
        {
            var compare = dist[x].CompareTo(dist[y]);
            if (compare == 0)
            {
                return x.CompareTo(y);
            }
            return compare;
        }
    }
}