#include <vector>
#include <fstream>
#include <iterator>
#include <algorithm>

using namespace std;
typedef pair<int, int> pr;

const int NMAX = 50011;
const int oo   = 1 << 29;

int lHeap;
vector<pr> G[NMAX];
vector<pr>::iterator it, iend;
int d[NMAX], H[NMAX], P[NMAX];

inline void swap(int& x, int& y) {int aux = x; x = y; y = aux;}
void DownHeap(int k)
{
	for(int son = k << 1; k <= lHeap; k = son, son <<= 1)
	{
		if(son < lHeap && d[H[son + 1]] < d[H[son]])
			++son;
		if(d[H[k]] <= d[H[son]]) return;
		swap(H[k], H[son]);
		swap(P[k], P[son]);
	} 
}

void UpHeap(int k)
{
	for(int f = k >> 1, key = d[H[k]]; k > 1 && key < d[H[f]]; k = f, f >>= 1)
	{
		swap(H[k], H[f]);
		swap(P[k], P[f]);
	}
}

inline void push(int x)
{
	H[++lHeap] = x;
	P[x] = lHeap;
	UpHeap(lHeap);
}

inline int pop()
{
	int ans = H[1];
	P[H[1]] = -1;
	H[1] = H[lHeap--];
	P[H[1]] = 1;
	
	DownHeap(1);
	return ans;
}

int main()
{
	int N, M, x, y, c;
	ifstream in("dijkstra.in");
	ofstream out("dijkstra.out");
	
	for(in >> N >> M; M; --M)
	{
		in >> x >> y >> c;
		G[x].push_back(pr(y, c));
	}
	d[1] = 0;
	for(push(1); lHeap; )
	{
		x = pop();
		for(it = G[x].begin(), iend = G[x].end(); it < iend; ++it)
		{
			if(-1 == P[it->first]) continue;
			if(!P[it->first])
			{
				d[it->first] = d[x] + it->second;
				push(it->first);
			}
			else if(d[it->first] > d[x] + it->second)
				 {
					 d[it->first] = d[x] + it->second;
					 UpHeap(P[it->first]);
				 }
		}
	}
	copy(d + 2, d + N + 1, ostream_iterator<int>(out, " "));
	out << '\n';
	
	return EXIT_SUCCESS;
}