#include <fstream>
#include <queue>
#include <vector>
#define INF 50010010
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,D[50010];
bool viz[50010];

priority_queue< pair<long long,int>, vector<pair<long long,int> >, greater<pair<long long,int> > > h;
vector<pair<int,int> > L[50010];

int main(void){
    register int i,j,x,y,c;
    pair<long long,int> p,q;

    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y>>c;
        L[x].push_back(make_pair(c,y));
    }
    for(i=2;i<=n;i++)
        D[i]=INF;

    h.push(make_pair(0,1));

    while(!h.empty()){
        p=h.top();
        h.pop();
        if(viz[p.second])
            continue;
        for(i=0;i<L[p.second].size();i++){
            q=L[p.second][i];
            if(!viz[q.second] && D[q.second]>D[p.second]+q.first){
                D[q.second]=D[p.second]+q.first;
                h.push(make_pair(D[q.second],q.second));
            }
        }
        viz[p.second]=true;
    }

    for(i=2;i<=n;i++){
        if(D[i]==INF)
            D[i]=0;
        g<<D[i]<<" ";
    }
    return 0;
}