#include <cstdio>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

#define N 50005
#define inf 1<<30

struct nod {
	int varf;
	int cost;
	};

vector<nod> v[N];
int c[N];
bool vrf[N];

void bellmanford (int n){

	vector<int> d(n+1,inf);
	d[1]=0;
	queue<int> q;
	++c[1];
	vrf[1]=true;
	for(q.push(1);!q.empty();q.pop()){
		int x=q.front();
		vrf[x]=false;
		for(vector<nod>::iterator i=v[x].begin();i<v[x].end();++i){
			if(d[x]+(*i).cost<d[(*i).varf]){
				d[(*i).varf]=d[x]+(*i).cost;
				if(!vrf[(*i).varf]){
					q.push((*i).varf);
					vrf[(*i).varf]=true;
					++c[(*i).varf];
					}
				}
			}
		}
	for(int i=2;i<=n;++i)
        printf("%d ",d[i]==(inf)?0:d[i]);
	printf("\n");

	}

int main ()
{

	ifstream in ("dijkstra.in");
	freopen ("dijkstra.out","w",stdout);
	int n,m;
	in>>n>>m;
	for(int x,y,z;m;--m){
		in>>x>>y>>z;
		v[x].push_back((nod){y,z});
		}
	bellmanford (n);

	return 0;}