#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

int d[50100],N,M,x,y,c;
bool v[50100];
pair<int,int> m;

priority_queue < pair < int,int > > pq;

struct nod {
    int val, cost;
} n;

vector<nod> a[50100];

int main() {

    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    scanf("%d%d",&N,&M);
    
    for(int i=2;i<=N;++i) {
        d[i] = (1<<30);
    }

    d[1]=0;

    for(int i=1;i<=M;++i) {
        scanf("%d%d%d",&x,&y,&c);
        n.val = y;
        n.cost = c;
        a[x].push_back(n);
    }

    pq.push(make_pair(0,1));

    while(!pq.empty()) {

        m = pq.top();
        pq.pop();
        int x = m.second;
        v[x]=1;
        for(int i=0;i<a[x].size();++i) {
            n = a[x][i];
            if(!v[n.val]) {
                d[n.val]=min(d[n.val],n.cost + d[x]); 
                pq.push(make_pair(-d[n.val],n.val));
            }
        }
    }

    for(int i=2;i<=N;++i) {
        printf("%d ",d[i]);
        }
}