#include<cstdio>
#define inf 2000000003
#define maxn 50005
#include<queue>
#include<vector>
using namespace std;
vector <int> G[maxn],C[maxn];
queue <pair <int,int> > Q;
int n,m,d[maxn],x,y,c;
void dijkstra(){
    for(int i=2;i<=n;++i)
        d[i]=inf;
        d[1]=0;
    Q.push(make_pair(1,0));
    pair <int,int> A;
    while(!Q.empty()){
        A=Q.front();Q.pop();
int      nod=A.first;
   int   cost=A.second;
        for(int i=0;i<G[nod].size();++i){
int             y=G[nod][i];
            if(d[y]>C[nod][i]+cost){
                d[y]=C[nod][i]+cost;
                Q.push(make_pair(y,d[y]));
            }
        }
    }

}
int main(){
    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);
        G[x].push_back(y);
        C[x].push_back(c);
    }
    dijkstra();
    for(int i=2;i<=n;++i)
        if(d[i]!=inf)
            printf("%d ",d[i]);
        else
            printf("%d ",0);
    return 0;
}