#include <cstdio>
#include <queue>
#define maxl 50005
#include <vector>
#define inf 0x3f3f3f3f
#include <cstring>

using namespace std;

priority_queue <pair<int,int> > Q;
int N,M,d[maxl];
vector <pair<int,int> > G[maxl];

void Lesen(){
    scanf("%d %d",&N,&M);
    int x,y,z;
    while(M--){
        scanf("%d %d %d",&x,&y,&z);
        G[x].push_back(make_pair(y,z));
    }
}
void Dijkstra(){
    memset(d,inf,sizeof(d));
    d[1]=0;
    Q.push(make_pair(0,1));
    int x;
    while(!Q.empty()){
        x=Q.top().second;
        Q.pop();
        for(vector <pair<int,int> >::iterator it=G[x].begin();it!=G[x].end();++it){
            if(d[x]+it->second < d[it->first]){
                d[it->first] = d[x] + it->second;
                Q.push(make_pair(-d[it->first],it->first));
            }
        }
    }
    for(x=2;x<=N;++x)printf("%d ",d[x]);
    printf("\n");
}
int main(){
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    Lesen();
    Dijkstra();
    return 0;
}