//Infoarena

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define oo 0x3f3f3f3f

int nodes;
vector< vector< pair < int, int> > > List;

void read(const char * buff_file)
{
	fstream f(buff_file, ios::in);
	if (f==NULL)
	{
		cerr<<"ERROR!";
		exit(0);
	}
	else
	{
		f>>nodes;
		int edges;
		List.reserve(nodes+1);
		List.resize(nodes+1);
		f>>edges;
		
		int left, right, value;
		
		for (int i=1; i<=edges; ++i)
		{
			f>>left>>right>>value;
			List[left].push_back(make_pair(right, value));
		}
		f.close();
	}
}

int * used;
int * dest;

void set_nr(int temp[], int nr_temp=nodes, int value=0)
{
	for (int i=1; i<=nr_temp; ++i)
		temp[i]=value;
}

struct cmp
{
	bool operator() (const int & left, const int & right) const
	{
		if (dest[left] < dest[right])
			return 1;
		else
			return 0;
	}
};

void Dijkstra()
{
	used=new int[nodes+1];
	dest=new int[nodes+1];
	
	set_nr(used, nodes, 0);
	set_nr(dest, nodes, oo);
	
	used[1]=1;
	dest[1]=0;
	
	priority_queue<int, vector<int>, cmp> Q;
	
	for (vector<pair<int, int> >::iterator it=List[1].begin(); it < List[1].end(); it++)
	{
		dest[it->first] = it->second;
		Q.push(it->first);
	}

	for (int i=1; (i<=nodes-1)&&(!Q.empty()); ++i)
	{
		int x=Q.top();
		Q.pop();
		//cout<<x<<" ";
		if (used[x]==0)
		{
			for (vector<pair<int, int> >::iterator it=List[x].begin(); it < List[x].end(); it++)
			{
				if (dest[it->first] > dest[x] + it->second ) 
				{
					dest[it->first]=dest[x]+it->second;
					Q.push(it->first);
				}
			}
		}
		else
			--i;
	};
};

void print(const char * out_file)
{
	fstream g(out_file, ios::out);
	for (int i=2; i<=nodes; ++i)
		g<<dest[i]<<" ";
	g.close();
}

int main()
{
	read("dijkstra.in");
	Dijkstra();
	print("dijkstra.out");
	return 0;
}