caminho_economico.cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> adj[n+1];

    // priority queue min heap
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

    vector<long long> dist(n+1, LONG_LONG_MAX);

    for(int i = 0; i<m; i++){
        int a, b, w;
        cin >> a >> b >> w;

        adj[a].push_back({b, w});
    }

    // 1 = source
    dist[1] = 0;
    pq.push({dist[1], 1});

    while(!pq.empty()){
        int s = pq.top().second;
        long long d = pq.top().first;
        pq.pop();

        if(dist[s] < d){
            continue;
        }

        for(auto v : adj[s]){
            int u = v.first;
            int w = v.second;

            if(dist[s] + w < dist[u]){
                dist[u] = dist[s] + w;
                pq.push({dist[u], u});
            }
        }
    }

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

    cout << endl;

    return 0;
}