#include<bits/stdc++.h>
using namespace std;
priority_queue< pair<int, int>, vector<pair<int, int> >, greater < pair <int, int > > > heap;
int dist[50001];
vector<pair<int,int> >v[250001];
int n;
void dijkstra ( int nod ){
    int d,to,i,from,edge;
    heap.push(make_pair(0,1));
    for(i=1;i<=n;i++)
        dist[i]=999999999;
    dist[nod]=0;
    while(!heap.empty()){
        from=heap.top().second;
        d=heap.top().first;
        heap.pop();
        if (dist[from] != d)
        {
            continue;
        }
        for(i=0;i<v[from].size();i++){
            to=v[from][i].second;
            edge=v[from][i].first;
            if(dist[to]>d+edge){
                dist[to]=d+edge;
                heap.push(make_pair(d+edge,to));
            }
        }
    }
}
int main(){
    int i,a,b,c,m;
    ifstream cin ("dijkstra.in");
    ofstream cout ("dijkstra.out");
    cin >> n >> m;
    for(i=1;i<=m;i++){
        cin >> a >> b >> c;
        v[a].push_back(make_pair(c,b));
    }
    dijkstra(1);
    for(i=2;i<=n;i++)
        if (dist[i] == 999999999)
            cout << "0 ";
        else cout << dist[i] << " ";
    return 0;
}