#include<fstream>
#include<queue>
#include<algorithm>
using namespace std;
#define inf 1<<20
typedef vector<int> VI;
//vector<VI> c;

int c[100][100];
VI d;
int n,s=1,m;
void citire ()
{
	ifstream fin("dijkstra.in");
	
	fin>>n>>m;
	int i,a,b,cost,j;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			c[i][j]=inf;
	for(i=1;i<=m;i++)
	{
		fin>>a>>b>>cost;
		c[a][b]=cost;
	}
	fin.close();
}
struct comp
{
	bool operator()(int i,int j)
{
	return d[i]<d[j];
	}
};
priority_queue<int,VI,comp> q;
void dijkstra(int nod)
{
	d.assign(n+1,inf);
	d[nod]=0;
	q.push(nod);
	int k,i;
	while(!q.empty())
	{
		k=q.top();
		q.pop();
		for(i=1;i<=n;i++)
			if(d[i]>d[k]+c[k][i])
			{
				d[i]=d[k]+c[k][i];
				q.push(i);
			}
	}
}
void scrie()
{
	ofstream fout("dijkstra.out");
	int i;
	for(i=2;i<=n;i++)
		fout<<d[i]<<' ';
	fout.close();
}
int main()
{
	citire();
	dijkstra(s);
	scrie();
	return 0;
}