class iPair{
    int first, second;
    public iPair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
class Pair 
{
    int distance, node;
    public Pair(int distance, int node)
    {
        this.distance = distance;
        this.node = node;
    }
}
 
class Solution {
    public List<Integer> shortestPath(int n, int m, int edges[][]) {
 
        // Step-1 create an adjacency list
        ArrayList<ArrayList<iPair>> adj = new ArrayList<>();
        for(int i=0;i<=n;i++)
        {
            adj.add(new ArrayList<iPair>());
        }
 
        for(int[] edge : edges)
        {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            adj.get(u).add(new iPair(v,w));
            adj.get(v).add(new iPair(u, w));
        }
 
        // Step-2 Create a distance array and parent node array
        int[] distance = new int[n+1];
        int[] parent = new int[n+1];
        for(int i=0;i<=n;i++)
        {
            distance[i] = (int)1e9;
            parent[i] = i;
        }
        distance[1] = 0;
 
        // Step-3 Store the nodes into MIN-HEAP accoriding to node's weight
        PriorityQueue<Pair> pq = new PriorityQueue<Pair>((x,y) -> Integer.compare(x.distance, y.distance));
        pq.add(new Pair(0, 1));
 
        // Step-4 Traverse the nodes present in min-heap
        while(pq.size()!=0)
        {
            Pair pair = pq.poll();
            int currentNode = pair.node;
            int currentDist = pair.distance;
 
            for(iPair neighbour : adj.get(currentNode))
            {
                int adjNode = neighbour.first;
                int weight = neighbour.second;
 
                if(distance[adjNode] > (currentDist + weight))
                {
                    distance[adjNode] = currentDist + weight;
                    pq.add(new Pair(distance[adjNode], adjNode));
                    parent[adjNode] = currentNode;
                }
            }
        }
 
        List<Integer> arr = new ArrayList<>();
        if(distance[n] == 1e9)
        {
            arr.add(-1);
            return arr;
        }
 
        // Backtrack from destination to source
        int node = n;
        // Use the parent[] array to trace back the path
        /**
         * If path is:
            1 → 2 → 4 → 5
            
            Then:
            parent[5] = 4
            parent[4] = 2
            parent[2] = 1
            parent[1] = 1
            
            Loop will:
            add 5
            add 4
            add 2
            (stop at 1 because parent[1] == 1)
         **/
        while(parent[node] != node)
        {
            arr.add(node);
            node = parent[node];
        }
        // Because the loop stops before adding node 1, we add it explicitly.
        arr.add(1);
        // Add total distance
        arr.add(distance[n]);
 
        Collections.reverse(arr);
        return arr;
    }
}