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

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
const int INF=1000000000;
const int NMAX=50000;

vector <ii> G[NMAX+5];
int main()
{
	int n,i,m,s,u,v,w,d,j;
	fin>>n>>m;
	for(i=1;i<=m;i++)
		{fin>>u>>v>>w;
		 G[u].push_back(ii(v,w));
		}
	vi dist(n+1,INF);
	dist[1]=0;
	priority_queue< ii,vector<ii>,greater<ii> > pq;
    pq.push(ii(0,1));
    while(!pq.empty())
    {
    	ii front=pq.top();
    	pq.pop();
		d=front.first;
    	u=front.second;
    	if(d>dist[u])
		   continue;
		for(j=0;j<(int)G[u].size();j++)
			{
				int v=G[u][j].first,duv=G[u][j].second;
				if(dist[u]+duv<dist[v])
				   {dist[v]=dist[u]+duv;
					pq.push(ii(dist[v],v));
				   }
			}
    }
    for(i=2;i<=n;i++)
		if(dist[i]==INF)
			fout<<"0 ";
		else
		fout<<dist[i]<<" ";
    return 0;
}