#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <bitset>
using namespace std;

#define INF 0x3f3f3f3f

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n, m, x, y, c, t;
int d[50010];
vector < pair <int, int> > a[50010];
queue <int> q;
bitset <50010> b;

int main(){
    fin>>n>>m;
    for(;m;--m){
        fin>>x>>y>>c;
        a[x].push_back(make_pair(y, c));
    }
    q.push(1);
    memset(d, INF, sizeof(d));
    d[1]=0;
    while(q.size()){
        t=q.front();
        b[t]=1;
        q.pop();
        for(int i=0;i<a[t].size();++i){
            int gg=a[t][i].first;
            d[gg]=min(d[gg], d[t]+a[t][i].second);
            if(!b[gg]) q.push(gg);
        }
    }
    for(int i=2;i<=n;++i){
        if(d[i]!=INF) fout<<d[i]<<' ';
        else fout<<0<<' ';
    }

    return 0;
}