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;
        }
    
        int node = n;
        while(parent[node] != node)
        {
            arr.add(node);
            node = parent[node];
        }

        arr.add(1);
        arr.add(distance[n]);
        
        Collections.reverse(arr);
        return arr;
    }
}