#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
#include <set>
//#include <algorithm>
using namespace std;
bool *visited;
vector<int>  *adj;
vector<int> *cost;
int* path;
vector<int > Q;
int *heapIndex;
int count;
void push(int k,int index)
{	
	int p = (index-1)>>1;
	while (index>0 && path[Q[p]]>path[Q[index]])
	{
	  int swapp = Q[index];
	  Q[index] = Q[p];
	  Q[p]=swapp;
	  heapIndex[Q[index]] = index;	  
	  index = p;	 
	  p = (index-1)>>1;
	}
	heapIndex[Q[index]] = index;
}
int pop()
{
	int p = Q.front();
	Q[0]=Q[Q.size()-1];
	heapIndex[Q[0]]=0;
	Q.pop_back();
	int index = 0;
	int minindex;
	bool swap;
	while(true){
		minindex = index;
		int left = (index<<1)+1;
		int right = left+1;
		if (left<Q.size() && path[Q[left]]<path[Q[index]])
			minindex = left;
		if (right<Q.size() &&path[Q[right]]<path[Q[minindex]])
			minindex = right;
		if (minindex!=index)
		{
			int swapp = Q[minindex];
			Q[minindex] = Q[index];
			Q[index] = swapp;
			heapIndex[Q[index]] = index;	
			heapIndex[Q[minindex]] = minindex;
			swap = true;
		}
		else return p;
		index = minindex;
	};
	return 0;
}
void dijkstra(int n)
{
	while (!Q.empty()){
		int cst,k;
		int fe= pop();
		cst = path[fe];
		k = fe;	
		visited[k]=true;
		for (int i=0;i<adj[k].size();i++)
		{
			if (!visited[adj[k][i]])
				{
					int s=cost[k][i]+cst;
					if (path[adj[k][i]]==INT_MAX){
						int t= adj[k][i];
						path[adj[k][i]] = s;
						Q.push_back(t);
						int index = Q.size()-1;
						push(adj[k][i],index);
					}
					else if (path[adj[k][i]]>s)
					{
						int index = heapIndex[adj[k][i]];
						path[adj[k][i]] = s;
						push(adj[k][i],index);
					}
				}			
		}
	}
}
int main()
{
	FILE *f = fopen("dijkstra.in","r");
	FILE *g = fopen("dijkstra.out","w+");
	int n,m;
	fscanf(f,"%d %d",&n,&m);
	adj = new vector<int>[n+1];
	visited=new bool[n+1];
	path=new int[n+1];
	cost=new vector<int>[n+1];
	heapIndex=new int[n+1];
	for (int i=0;i<=n;i++){
		visited[i]= false;
		path[i] = INT_MAX;
	}
	for (int i=0;i<m;i++)
	{
		int a,b,c;
		fscanf(f,"%d %d %d", &a,&b,&c);
		adj[a].push_back(b);		
		cost[a].push_back(c);
	}
	Q.reserve(n);
	Q.push_back(1);	
	path[1]=0;
	dijkstra(n);
	for (int i=2;i<=n;i++)
		if (path[i]==INT_MAX)
			fprintf(g,"0 ");
		else
			fprintf(g,"%d ",path[i]);
	fclose(f);
	fclose(g);
}