#include <cstdio>
#include <set>
#include <vector>
#define MAX 50001
#define INF 0xfffff
using namespace std;
vector<pair<int,int> >U[MAX];
set<pair<int,int> >S;
int n,m,C[MAX];

void dijkstra(){
    int x,y,c;
    for(int i=2;i<=n;i++)C[i]=INF;
    S.insert(make_pair(0,1));
    while(S.size()>0){
        c=S.begin()->first;
        x=S.begin()->second;
        S.erase(S.begin());
        for(int i=0;i<U[x].size();i++){
            y=U[x][i].first;
            if(C[y]>c+U[x][i].second){
                C[y]=c+U[x][i].second;
                S.insert(make_pair(c+U[x][i].second,y));
            }
        }
    }
}

int main(){
    int x,y,c;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
        scanf("%d %d",&n,&m);
        for(int i=1;i<=m;i++){
            scanf("%d %d %d",&x,&y,&c);
            U[x].push_back(make_pair(y,c)); }
    dijkstra();
        for(int i=2;i<=n;i++)printf("%d ",C[i]==INF?0:C[i]);
}