#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = 1e9;

// Dijkstra cu heap
vector<int> dijkstra(int n, int s, const vector<vector<pair<int,int>>>& adj, vector<int>& tata) {
    vector<int> d(n+1, INF);
    tata.assign(n+1, 0);
    d[s] = 0;

    // Min-heap: (distanta, nod)
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [distU, u] = pq.top(); pq.pop();

        if (distU > d[u]) continue; // stare veche

        for (auto [v, cost] : adj[u]) {
            if (d[u] + cost < d[v]) {
                d[v] = d[u] + cost;
                tata[v] = u;
                pq.push({d[v], v});
            }
        }
    }

    return d;
}

// reconstrucția drumului
vector<int> reconstructPath(int s, int t, const vector<int>& tata) {
    vector<int> path;
    int nod = t;
    while (nod != 0) {
        path.push_back(nod);
        if (nod == s) break;
        nod = tata[nod];
        if (nod == 0 && path.back() != s) {
            path.clear();
            break;
        }
    }
    reverse(path.begin(), path.end());
    return path;
}

int main() {
    int n, m, s;
    cout << "Numarul de noduri este: "; cin >> n;
    cout << "Numarul de muchii este: "; cin >> m;
    cout << "Nodul sursa este: " ; cin >> s;

    vector<vector<pair<int,int>>> adj(n+1);
    for (int i = 0; i < m; i++) {
        int u, v, cost;
        cout << "Muchia este de la: "; cin >> u; cout << "la: "; cin >> v; cout << "de cost: "; cin>> cost;
        adj[u].push_back({v, cost});
        // adj[v].push_back({u, cost}); // daca graful e neorientat
    }

    vector<int> tata;
    vector<int> d = dijkstra(n, s, adj, tata);

    for (int i = 1; i <= n; i++) {
        cout << "d[" << i << "] = " << d[i] << "\n";
    }

    int t;
    cout << "Nodul tinta este: "; cin >> t;

    vector<int> path = reconstructPath(s, t, tata);
    if (!path.empty()) {
        cout << "Drumul minim de la " << s << " la " << t << " este: ";
        for (int x : path) cout << x << " ";
        cout << "\n";
    } else {
        cout << "Nu exista drum de la " << s << " la " << t << "\n";
    }

    return 0;
}