#include <bits/stdc++.h>]
#define nmax 500005
#define INF 2000000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector< pair< int, int> >g[nmax];
int d[nmax];
void Dijkstra(){
    priority_queue <pair <int, int> , vector <pair <int, int> >, greater <pair <int, int> > >pq;
    pq.push(make_pair(0,1));
    pair <int, int> it;
    int i;
    while(!pq.empty()){
        int node=pq.top().second;
        int value=pq.top().first;
        pq.pop();
        if(d[node]!=value) continue;
        for(i=0; i<g[node].size(); i++){
            it=g[node][i];
            if(value + it.second < d[it.first]){
                d[it.first]=value + it.second;
                pq.push(make_pair(d[it.first], it.first));
            }

        }
    }
}
int main()
{
    int n,m,x,y,i,cost;
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y>>cost;
        g[x].push_back(make_pair(y,cost));
    }
    for(i=2;i<=n;i++)
        d[i]=INF;
    Dijkstra();
    for(i=2;i<=n;i++){
        if(d[i]==INF) fout<<"0 ";
        else fout<<d[i]<<" ";
    }
    return 0;
}