#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
#define buffersize 32765
using namespace std;
struct lista { int cost,m; lista *next; };
int n,m,x,y,z,i,l,d[nmax],heap[nmax],pos[nmax],nr;
lista *a,*t[nmax];
bool ok=true;
char buffer[buffersize+2];
void read(int &x)
{
    if (ok){
        ok=false; l=0;
        fread(buffer,1,buffersize,stdin);
    }
    x=0;
    while (buffer[l]-48<0 || buffer[l]-48>9) {
        l++;
        if (l==buffersize){
            fread(buffer,1,buffersize,stdin);
            l=0;
        }
    }
    while (buffer[l]>='0' && buffer[l]<='9'){
        x=x*10+(buffer[l]-48); l++;
        if (l==buffersize){
            fread(buffer,1,buffersize,stdin);
            l=0;
        }
    }
}
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);
read(n); read(m);
for (i=1;i<=m;i++){
    read(x); read(y); read(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;
}