#include <fstream>
#include <vector>
#include <queue>
#define inf 2100000000
using namespace std;

struct s_node
{
vector <int> ad;
vector <int> cost;
int val;
};

int n,m;
s_node node[50000]; //graf ORIENTAT!
queue <int> nodeq;

int main()
{
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int i1,a,b,c;
bool lsw1=false;
vector<int>::iterator it1;
vector<int>::iterator it2;

in>>n>>m;

for(i1=1;i1<n;i1++)
	node[i1].val=inf;

for(i1=0;i1<m;i1++)
	{
	in>>a>>b>>c;
	a--; b--;
	node[a].ad.push_back(b);
	node[a].cost.push_back(c);
	}

nodeq.push(0);
while(!nodeq.empty())
	{
	for(it1=node[nodeq.front()].ad.begin(),it2=node[nodeq.front()].cost.begin() ; it1 != node[nodeq.front()].ad.end() ; it1++, it2++ )
		{
		//it1 = id-ul nodului adiacent
		//it2 = costul asociat
		lsw1=false;
		if(node[*it1].val > node[nodeq.front()].val + *it2)
			lsw1=true;
		if(lsw1)
			{
			node[*it1].val = node[nodeq.front()].val + *it2;
			nodeq.push(*it1);
			}
		}
	nodeq.pop();
	}
for(i1=1;i1<n;i1++)
	out<<node[i1].val<<' ';

in.close();
out.close();
return 0;
}