#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;


void open(){
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
}

#define pb push_back
#define sz size()
#define MAXN 50010
#define x first
#define y second
typedef pair<int,int>pii;
typedef vector<pii>vii;
struct cf{
    bool operator()(const pii &a,const pii &b)const{
        return (a.y>b.y);
    };
};
const int oo=(int)1e9;
int n,m,a,b,c,l[MAXN];
vii g[MAXN];

int main(){
    open();
    scanf("%d%d",&n,&m);
    for (int i=0;i<m;i++){
        scanf("%d%d%d",&a,&b,&c);
        g[a].pb(pii(b,c));
    }
    for (int i=1;i<=n;i++) l[i]=oo;
    l[1]=0;
    priority_queue<pii,vii,cf>q;
    q.push(pii(1,0));
    while (!q.empty()){
        pii top=q.top();
        q.pop();
        int v=top.x;
        int d=top.y;
        if (d<=l[v]){
            for (vii::iterator it=g[v].begin();it!=g[v].end();it++){
                if (l[it->x]>l[v]+it->y){
                    l[it->x]=l[v]+it->y;
                    q.push(pii(it->x,l[it->x]));
                }
            }
        }
    }
    for (int i=2;i<=n;i++){
        if (i>2) printf(" ");
        if (l[i]==oo) l[i]=0;
        printf("%d",l[i]);
    }
    printf("\n");
    //system("pause");
    return 0;
}