#include <fstream>
#include <iostream>
#include <cstdio>
#include <bitset>
#include <vector>

const long infinit=2147483647;

using namespace std;

int main()
{
	//cout<<"aaaaaaaaaaaaaaaaaa";
	int n,m,x,y,z,i,j;
	ifstream f("dijkstra.in");
	f>>n>>m;
	int drum[715];
	bitset <715> selected;
	int a[715][715];
	int parinte[1000];
	for (i=0; i<715; i++)
		for (j=0; j<715; j++)
			a[i][j]=-1;
	/*vector <int> drum;         // }
 	vector <short> selected; //  }
	vector <int> parinte;    //   }
	vector <vector<int> > a;
	drum.reserve(n+1);
	selected.reserve(n+100);
	parinte.reserve(n+100);
	a.reserve(n+100);
	for (i=0; i<n+100; i++)
		a[i].reserve(n+100);*/
	for (i=0; i<m; i++) {
		f>>x>>y>>z;
		a[x][y]=z;
	}
	f.close();
	for (i=1; i<=n; i++) {
		drum[i]=infinit;
		parinte[i]=1;
		selected[i]=0;
	}

	drum[1]=0;
	int dmin,nmin;
	while (true) {
		//cout<<dmin<<'\n';
		dmin=infinit;
		nmin=0;
		for (i=1; i<=n; i++)
			if (drum[i]<dmin && selected[i]==0) {
				dmin=drum[i];
				nmin=i;
			}
		if (dmin==infinit) break;
		selected[nmin]=1;
		for (i=1; i<=n; i++)
			if (a[nmin][i]!=-1 && selected[i]==0 && dmin+a[nmin][i]<drum[i]) {
				drum[i]=dmin+a[nmin][i];
				parinte[i]=nmin;
			}
	}
	freopen("dijkstra.out","w",stdout);
	for (i=2; i<=n; i++) 
		if (drum[i]==infinit) printf("%d ",0);
		else printf("%d ",drum[i]);
	return 0;
}