#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

const int MAXN = 50005;
const int INF = 1000000;

int n, m;
vector< pair<int, int> > G[MAXN];
int Dmin[MAXN];

void citeste() 
{
	ifstream f("dijkstra.in");

	f >> n >> m;
	for (int i = 0; i < m; ++i) 
    {
		int a, b, c;

		f >> a >> b >> c;
		G[a].push_back(make_pair(b, c));
	}
}

void dijkstra() 
{
	bool viz[MAXN];
                  
	queue<int> Q;  

	memset(Dmin, INF, sizeof(Dmin));
	memset(viz, false, sizeof(viz));

	Dmin[1] = 0;
	Q.push(1);
	viz[1] = true;

	while (!Q.empty()) 
    { 
		int nod = Q.front(); 
		Q.pop();       
		viz[nod] = false;

		for (vector< pair<int, int> >::iterator it = G[nod].begin(); it != G[nod].end(); ++it)
			if (Dmin[nod] + it->second < Dmin[it->first]) 
            {
				Dmin[it->first] = Dmin[nod] + it->second;
				
				if (!viz[it->first]) 
                {
					Q.push(it->first);
					viz[it->first] = true;
				}
		
        	}
        	
	}
}

void afisare() 
{
	ofstream g("dijkstra.out");

	for (int i = 2; i <= n; ++i)
	
		g<< (Dmin[i] < INF ? Dmin[i] : 0) << " ";
}

int main() 
{
	citeste();
	dijkstra();
	afisare();
}