#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define FIN "dijkstra.in"
#define FOUT "dijkstra.out"
#define MAX_N 50005
#define INF 2000000000

vector<int> G[MAX_N];
vector<int> C[MAX_N];

int H[MAX_N], D[MAX_N], stat[MAX_N], adr[MAX_N], deg[MAX_N];
int N, M, k;

	void readdata ()
	{
		int i, a, b, c;
		scanf ("%d %d", &N, &M);
		for (i = 1; i <= M; ++i)
		{
			scanf ("%d %d %d", &a, &b, &c);
			G[a].push_back(b);
			C[a].push_back(c);
		}
		for (i = 1; i <= N; ++i) deg[i] = G[i].size () - 1;
	}
	
	void sink (int c)
	{
		while (c << 1 <= k)
		{
			int s = c << 1;
			if ((s|1) <= k && D[ H[s|1] ] < D[H[s]]) s |= 1;
			
			if (D[H[s]] < D[H[c]])
			{
				H[s] ^= H[c], H[c] ^= H[s], H[s] ^= H[c];
				
				adr[H[c]] = c, adr[H[s]] = s;
				c = s;
			}
			else return;
		}
	}
	
	void lift (int c)
	{
		while (c >> 1)
		{
			int t = c >> 1;
			if (D[H[t]] > D[H[c]])
			{
				H[t] ^= H[c], H[c] ^= H[t], H[t] ^= H[c];
				
				adr[H[c]] = c, adr[H[t]] = t;
				c = t;
			}
			else return;
		}
	}
	
	void erase (int c)
	{
		H[c] = H[k--];
		adr[H[c]] = c;
		sink (c);
	}
	
	void insert (int c)
	{
		stat[c] = 1;
		H[++k] = c;
		adr[c] = k;
		lift (k);
	}
	
	void solve ()
	{
		int i;
		for (i = 2; i <= N; ++i) D[i] = INF, stat[i] = 0;
		stat[1] = 1, adr[1] = 1;
		H[k = 1] = 1;
		while (k)
		{
			int min = H[1];
			erase (1);
			
			for (i = 0; i <= deg[min]; ++i)
				if (D[min] + C[min][i] < D[ G[min][i] ])
				{
					D[ G[min][i] ] = D[min] + C[min][i];
					if (stat[G[min][i]]) lift (adr[G[min][i]]);
						else insert (G[min][i]), lift(k);
				}
		}
		for (i = 2; i <= N; ++i)
			if (D[i] == INF) printf ("0 "); else printf ("%d ", D[i]);
	}

	int main ()
	{
		freopen (FIN, "r", stdin);
		freopen (FOUT, "w", stdout);
		
		readdata ();
		solve ();
		
		return 0;
	}