#include<stdio.h>
#include<fstream>
#include<vector>
#include<queue>
#include<bitset>
using namespace std;

#define MaxN 100100

typedef vector<pair <int,int> >::iterator it;

vector<pair <int,int> > A[MaxN];
int viz[MaxN];
int Cost[MaxN];
int N;
int M;
int S;

void citire(void)
{
	int a;
	int b;
	int c;
	ifstream fin ("dijkstra.in");
	
	fin >> N >> M;
	for(long int i=1;i<=M;i++)
	{
		fin >> a >> b >> c;
		A[a].push_back(make_pair(b,c));
	}
}

void parcurgere(void)
{
	queue<int> Q;
	viz[1] = 1;
	for(Q.push(1);!Q.empty();Q.pop())
		for(it i=A[Q.front()].begin();i<A[Q.front()].end();i++)
			if(!Cost[i->first] || (Cost[Q.front()] + i->second<Cost[i->first]))
			{			
				Cost[i->first] = Cost[Q.front()] + i->second;
				if(!viz[i->first])
					Q.push(i->first);
			}
}

void afisare(void)
{
	FILE *f = fopen("dijkstra.out","w");
	
	for(long int i=2;i<=N;i++)
		fprintf(f,"%d ",Cost[i]);
	
	fclose(f);
}

int main()
{
	citire();
	parcurgere();
	afisare();
	return 0;
}