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

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;

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();
        q.pop();
        for(int i=0;i<a[t].size();++i){
            int gg=a[t][i].first;
            if(d[gg]>d[t]+a[t][i].second){
                d[gg]=d[t]+a[t][i].second;
                q.push(gg);
            }

        }
    }
    for(int i=2;i<=n;++i){
        if(d[i]!=INF) fout<<d[i]<<' ';
        else fout<<0<<' ';
    }

    return 0;
}