#include <iostream>
#include <fstream>
#define INFINIT 10000
#define nmax 50005
#define mmax 250005
using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

typedef struct
{
	int x, y, c;
} Edge;

int n, m, d[nmax];
Edge edges[mmax];


void citeste()
{
    in>>n>>m;
    for (int i=1; i<=m; ++i)
     {
         in>>edges[i].x>>edges[i].y>>edges[i].c;
     }
}


void bellman_ford(int s) {

	for (int i = 1; i <= n; ++i)
		d[i] = INFINIT;

	d[s] = 0;

	for (int i = 1; i < n; ++i)
		for (int j = 1; j <= m; ++j)
			if ( d[edges[j].x] + edges[j].c < d[edges[j].y])
				d[edges[j].y] = d[edges[j].x] + edges[j].c;
}

int main()
{

	citeste();

	bellman_ford(1);

	for (int i=2; i<=n; ++i)
     out<<d[i]<<" ";


return 0;
}