#include <stdio.h>
#include <set>
#include <vector>
#define INF 0x2FAF081
using namespace std;
struct nod{ int key,cost; };
bool comparator(nod a,nod b){ return a.cost<=b.cost; }
bool(*pointer)(nod,nod)=comparator;
set<nod,bool(*)(nod,nod)>s(pointer);
set<nod>::iterator it;
vector<nod>a[50005];
int cost[50005];

void dijkstra(){
    nod w;
    int val,x;
    w.key=1;
    w.cost=0;
    s.insert(w);
    while(s.size()>0){
        x=s.begin()->key; val=s.begin()->cost;
        s.erase(s.begin());
        for(int i=0;i<a[x].size();i++)
        if(cost[a[x][i].key]>val+a[x][i].cost){
           cost[a[x][i].key]=val+a[x][i].cost;
           w.key=a[x][i].key;
           w.cost=cost[a[x][i].key];
           s.insert(w); }
    }
}

int main(){
    int n,m,A,B,C;
    nod w;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
        scanf("%d %d",&n,&m);
    for(int i=2;i<=n;i++)cost[i]=INF;
    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&A,&B,&C);
        w.key=B;
        w.cost=C;
        a[A].push_back(w); }
    dijkstra();
    for(int i=2;i<=n;i++)printf("%d ",cost[i]==INF?0:cost[i]);
}