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

int n,m,s;
int a[100001];
int v[4][1000001];

void dijkstra (int nod)
{
	int i,b,j;
    for (i=1; i<=n; i++) a[i]=-1;
    a[nod]=0; b=1;
	while (b)
	{
	    b=0;
        for (i=1; i<=m; i++)
           if (a[v[1][i]]!=-1  && ( a[v[2][i]]==-1 || a[v[2][i]] > a[v[1][i]]+v[3][i] ))
              {
                  a[v[2][i]]=a[v[1][i]]+v[3][i];
                  b=1;
              }
    }
}

int main()
{
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	int i;
    scanf("%i%i",&n,&m);
    for (i=1; i<=m; i++)  scanf("%i%i%i",&v[1][i],&v[2][i],&v[3][i]);
    dijkstra(1);
    for (i=2; i<=n; i++)
     if (a[i]==-1) printf("0 "); else printf("%i ",a[i]);
    return 0;
}