#include <stdio.h>
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <time.h>
#include <bitset>
#include <string>
#include <vector>
#include <math.h>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <limits.h>
#include <algorithm>
#include <deque>
#define nmax 50010
#define inf 0x3f3f3f3f
using namespace std;
struct edge{ int m,cost; edge *next; };
int n,m,i,j,x,y,z,heap[nmax],pos[nmax],d[nmax],nr;
edge *t [nmax],*a;
void Swap(int &a,int &b)
{
    swap(a,b); swap(pos[a],pos[b]);
}
void heapup(int v)
{
    int k=heap[v];
    while (v>1 && d[heap[v]]<d[heap[v/2]]) {
        Swap(heap[v],heap[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(heap[v],heap[w]); else break;
        v=w; w=w*2;
    }
}
void delete_heap()
{
    Swap(heap[1],heap[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 edge; a->m=y; a->cost=z; a->next=t[x]; t[x]=a;
}
for (i=1;i<=n;i++) { heap[i]=i; pos[i]=i; d[i]=inf; }
nr=n; d[1]=0;
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;
}