//Ce stil am ;x
//Include
#include <stdio.h>
#include <limits.h>
#include <queue>
#include <vector>
#include <utility>
using namespace std;

//Definitii
#define cost first
#define dest second
#define indice second

//Constante
const int MAX_SIZE=50001;

//Functii
void dijkstra(int start);

//Variabile
FILE *in, *out;

int noduri, muchii;

vector<pair<int, int> > graf[MAX_SIZE];
vector<pair<int, int> >::iterator it, end;
vector<int> dist(MAX_SIZE, INT_MAX);
priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > q;

//Main
int main()
{
	in=fopen("dijkstra.in","rt");
	out=fopen("dijkstra.out","wt");
	fscanf(in, "%d%d", &noduri, &muchii);
	
	int c_from, c_to, c_cost;
	for(int i=1 ; i<=muchii ; ++i)
	{
		fscanf(in, "%d%d%d",&c_from, &c_to, &c_cost);
		graf[c_from].push_back( make_pair(c_cost, c_to) );
	}
	
	dijkstra(1);
	
	for(int i=2;i<=noduri;++i)
		if(dist[i]==INT_MAX)
			fprintf(out, "0 ");
		else
			fprintf(out, "%d ",dist[i]);
	
	
	fclose(in);
	fclose(out);
	return 0;
}

void dijkstra(int start)
{
	dist[start] = 0;
	q.push(make_pair(0, start));
	while(!q.empty())
	{
		pair<int, int> curent=q.top();
		q.pop();
		end = graf[curent.indice].end();
		for(it=graf[curent.indice].begin() ; it!=end ; ++it)
		{
			if(dist[curent.indice] + it->cost < dist[it->dest])
			{
				dist[it->dest] = dist[curent.indice] + it->cost;
				q.push(make_pair(dist[it->dest], it->dest));
			}
		}
	}
}


//Ce stil am ;x