#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <limits.h>
#include <set>
#define nmax 50010
#define inf 9999999
using namespace std;
struct lista { int cost,m; lista *next; };
int n,m,x,y,z,i,d[nmax],heap[nmax],pos[nmax],nr;
lista *a,*t[nmax];
void Swap(int x,int y)
{
    swap(heap[x],heap[y]); swap(pos[heap[x]],pos[heap[y]]);
}
void heapup(int v)
{
    int k=heap[v];
    while (v>1 && d[heap[v]]<d[heap[v/2]]){
        Swap(v,v/2);
        v=v/2;
    }
    heap[v]=k;
}
void heapdown(int v)
{
    int w=v*2;
    while (w<=nr){
        if (w+1<=nr && d[heap[w+1]]<d[heap[w]]) w++;
        if (d[heap[v]]>d[heap[w]]) Swap(v,w); else break;
        v=w; w=w*2;
    }
}
void delete_heap()
{
    Swap(1,nr); nr--;
    heapdown(1);
}
int main(){
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++){
    scanf("%d%d%d",&x,&y,&z);
    a=new lista; a->m=y; a->cost=z; a->next=t[x]; t[x]=a;
}
for (i=1;i<=n;i++) { d[i]=inf; heap[i]=i; pos[i]=i; }
d[1]=0; nr=n;
while (nr>0){
    x=heap[1]; delete_heap(); a=t[x];
    while (a){
        if (d[x]+a->cost<d[a->m]){
            d[a->m]=d[x]+a->cost; heapup(pos[a->m]);
        }
    a=a->next;
    }
}
for (i=2;i<=n;i++)
    if (d[i]==inf) printf("0 "); else
        printf("%d ",d[i]);
return 0;
}