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

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

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

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