easy

#include <iostream> 
#include <vector> 
#include <queue> 
#include <climits> 
 
using namespace std; 
 
const int MAXN = 10005; 
const int MAXM = 200005; 
 
// 边的结构体 
struct Edge { 
    int to; 
    int cost; 
    Edge(int t, int c) : to(t), cost(c) {} 
}; 
 
// 优先队列中的元素结构体 
struct Node { 
    int u; 
    int dist; 
    int pathLen; 
    vector<int> path; 
    Node(int _u, int _dist, int _pathLen, vector<int> _path) : u(_u), dist(_dist), pathLen(_pathLen), path(_path) {} 
    bool operator>(const Node& other) const { 
        return dist > other.dist;  
    } 
}; 
 
vector<Edge> graph[MAXN]; 
int dist[MAXN]; 
bool visited[MAXN]; 
 
// Dijkstra算法 
pair<int, vector<int>> dijkstra(int n) { 
    priority_queue<Node, vector<Node>, greater<Node>> pq; 
    fill(dist, dist + n + 1, INT_MAX); 
    fill(visited, visited + n + 1, false); 
 
    vector<int> initPath = {1}; 
    pq.push(Node(1,  0, 0, initPath)); 
    dist[1] = 0; 
 
    while (!pq.empty())  { 
        Node cur = pq.top();  
        pq.pop();  
        int u = cur.u; 
        int d = cur.dist;  
        int pathLen = cur.pathLen;  
        vector<int> path = cur.path;  
 
        if (visited[u]) continue; 
        visited[u] = true; 
 
        if (u == n) { 
            return make_pair(d, path); 
        } 
 
        for (const Edge& edge : graph[u]) { 
            int v = edge.to;  
            int newDist = d + edge.cost  + pathLen; 
            if (!visited[v] && newDist < dist[v]) { 
                dist[v] = newDist; 
                vector<int> newPath = path; 
                newPath.push_back(v);  
                pq.push(Node(v,  newDist, pathLen + 1, newPath)); 
            } 
        } 
    } 
 
    return make_pair(-1, vector<int>()); 
} 
 
int main() { 
    int n, m; 
    cin >> n >> m; 
 
    for (int i = 0; i < m; i++) { 
        int a, b, c; 
        cin >> a >> b >> c; 
        graph[a].emplace_back(b, c); 
    } 
 
    pair<int, vector<int>> result = dijkstra(n); 
    int shortestTime = result.first;  
    vector<int> path = result.second;  
 
    cout << shortestTime << endl; 
    for (int i = 0; i < path.size();  i++) { 
        if (i > 0) cout << " "; 
        cout << path[i]; 
    } 
    cout << endl; 
 
    return 0; 
}