#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

struct Info {
    int node;
    int weight;
};

struct HeapNode {
    int node;
    int nr;
    inline bool operator<(const HeapNode &a) const {
        return nr>a.nr;
    }
};

int n,m;
vector<vector<Info>> graph;
priority_queue<HeapNode> q;
vector<int> dist;

void read() {
    cin>>n>>m;
    graph.resize(n+1);
    dist.resize(n+1,2e9);
    int a,b,w;
    for(int x=1;x<=m;x++) {
        cin>>a>>b>>w;
        graph[a].push_back({b,w});
    }
}

void solve() {
    dist[1]=0;
    q.push({1,0});
    while(!q.empty()) {
        HeapNode a=q.top();
        q.pop();
        dist[a.node]=a.nr;
        for(auto i:graph[a.node]) {
            if(dist[i.node]>dist[a.node]+i.weight) {
                dist[i.node]=dist[a.node]+i.weight;
                q.push({i.node,dist[i.node]});
            }
        }
    }
    for(int i=2;i<=n;i++) {
        if(dist[i]==2e9) {
            cout<<"0 ";
            continue;
        }
        cout<<dist[i]<<" ";
    }
}

int main() {
 
    read();
    solve();
    return 0;
}