#include<fstream>
#include<vector>
#include<utility>
#include<queue>
#define NN 50001
#define INF 0x3f3f3f3f

#define pb push_back
#define ff first
#define ss second
#define mp make_pair

using namespace std;
ofstream out("dijkstra.out");
vector<pair<int,int> >G[NN];
queue<int>Q;
vector<int>d(NN,INF);

int n,m;
void read();
void dijkstra(int);

int main()
{
	read();
	dijkstra(1);
	d[1]=0;
	for(int i=2;i<=n;i++)
		out<<(d[i]==INF?0:d[i])<<" ";
	return 0;
	
}
void read()
{
	ifstream in("dijkstra.in");
	in>>n>>m;
	int i,j,c;
	for(;m;--m)
	{
		in>>i>>j>>c;
		G[i].pb(mp(j,c));
	}
}

void dijkstra(int start)
{
	d[start]=0;
	Q.push(start);
	while(!Q.empty())
	{
		int k=Q.front();
			for(int i=0;i<G[k].size();++i)
				if(d[G[k][i].ff]>d[k]+G[k][i].ss)
				{
					d[G[k][i].ff]=d[k]+G[k][i].ss;
					Q.push(G[k][i].ff);
				}
				Q.pop();
	}
	
}