#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[50001]; //graf ORIENTAT!

class cmp
{
public:
	bool operator()(int& a,int& b)
		{
		if(node[a].val > node[b].val) return true;
		return false;
		}
};

priority_queue <int, vector<int>, cmp> 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=2;i1<=n;i1++)
	node[i1].val=inf;

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

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