#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <list>
#include <algorithm>
#define MAXINT 1000000000
using namespace std;
struct  node
{
	int to,dist;
};
typedef list<node> LIST_OF_NODES;
typedef vector<LIST_OF_NODES> VECTOR_OF_LIST_OF_NODES;
typedef vector<vector<int> > VECTOR_OF_VECTORS_OF_INTS;

FILE *fin=fopen("dijkstra.in","r");
FILE *fout=fopen("dijkstra.out","w");

void show_adj(VECTOR_OF_LIST_OF_NODES& adj_list,int n)
{
	for(int i=1;i<=n;i++)
	{
		cout<<i<<": ";
		for(LIST_OF_NODES::iterator it=adj_list[i].begin();it!=adj_list[i].end();it++)
		{
			cout<<"("<<(*it).to<<" : "<<(*it).dist<<") ";
		}
		cout<<endl;
	}
}

void ins(vector<int> &vec,VECTOR_OF_VECTORS_OF_INTS &dist, int curr, int element)
{
	vec.push_back(element);
	int index=vec.size()-1;
	while(dist[curr][vec[index]]<dist[curr][vec[index/2]])
	{
		swap(vec[index],vec[index/2]);
	}

}
int take_min(vector<int> &vec,VECTOR_OF_VECTORS_OF_INTS &dist, int curr)
{
	int M=vec.front();
	vec.front()=vec.back();
	vec.pop_back();
	int index=0;
	while(((2*index+1<vec.size()) && dist[curr][vec[index]]>dist[curr][vec[2*index+1]])||((2*index+2<vec.size()) &&(dist[curr][vec[index]]>dist[curr][vec[2*index+2]])))
	{
		if(dist[curr][vec[index]]>dist[curr][vec[2*index+1]])
			{swap(vec[index],vec[2*index+1]);
				index=2*index+1;}
		else
		{
			swap(vec[index],vec[2*index+2]);
				index=2*index+2;
		}

	}

	return M;
}
void dijkstra(int s,int n, VECTOR_OF_VECTORS_OF_INTS &dists,VECTOR_OF_LIST_OF_NODES &adj_list)
{
	vector<int> priority_q;
	priority_q.push_back(s);
	dists[s][s]=0;
	while(!priority_q.empty())
	{
		int curr=take_min(priority_q,dists,s);
		for(LIST_OF_NODES::iterator it=adj_list[curr].begin();it!=adj_list[curr].end();it++)
		{
			if(dists[s][(*it).to]>(dists[s][curr]+(*it).dist))
			{
				dists[s][(*it).to]=dists[s][curr]+(*it).dist;
				ins(priority_q,dists,s,(*it).to);
			}
		}
	}

}

void show_dist(VECTOR_OF_VECTORS_OF_INTS &dists,int n, int s)
{
	for(int i=1;i<=n;i++)
	{
		if(i!=s)fprintf(fout,"%d ",dists[s][i]);
	}
}

int main()
{
	int n,m;
	fscanf(fin,"%d %d",&n,&m);
	VECTOR_OF_LIST_OF_NODES adj_list(m+4);
	VECTOR_OF_VECTORS_OF_INTS dists(n+3,vector<int>(n+3,MAXINT));
	node tmp;
	int from, to, dist;
	for(int i=1;i<=m;i++)
	{
		fscanf(fin,"%d %d %d",&from,&to,&dist);
		tmp.to=to;
		tmp.dist=dist;
		adj_list[from].push_back(tmp);
		tmp.to=from;
		adj_list[to].push_back(tmp);
	}
	//show_adj();
	dijkstra(1,n,dists,adj_list);
	show_dist(dists,n,1);

	return 0;
}