Dijkstra

#include <queue>
#include <iostream>

using namespace std;
constexpr int INF = 2000000000;
typedef std::pair<int, int> PII;

int main( ) {
    int N, s, t;
    std::cin >> N >> s >> t;
    std::vector<std::vector<PII>> edges(N);
    for (int i = 0; i < N; ++i) {
        int M;
        std::cin >> M;
        for (int j = 0; j < M; ++j) {
            int vertex, dist;
            std::cin >> vertex >> dist;
            edges[i].push_back(std::make_pair(dist, vertex));
        }
    }

    std::priority_queue<PII, std::vector<PII>, std::greater<PII>> Q;
    std::vector<int> dist(N, INF), dad(N, -1);

    Q.push(std::make_pair(0, s));
    dist[s] = 0;
    while (!Q.empty( )) {
        PII p = Q.top( );
        Q.pop( );

        int here = p.second;
        if (here == t) break;
        if (dist[here] != p.first) continue;

        for (auto it = edges[here].begin( ); it != edges[here].end( ); ++it) {
            if (dist[here] + it->first < dist[it->second]) {
                dist[it->second] = dist[here] + it->first;
                dad[it->second] = here;
                Q.push(std::make_pair(dist[it->second], it->second));
            }
        }
    }

    std::cout << dist[t] << "\n";
    if (dist[t] < INF) {
        for (int i = t; i != -1; i = dad[i]) {
            std::cout << i << (i == s ? '\n' : ' ');
        }
    }
}