#include <fstream>
#include <vector>
#include <list>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,sursa,dest;
vector < pair<int,int> > vecini[50001]; 
int dist[50001],poz[50001];
vector <int> heap;
void sift(int k)
{
	int son; son=k; 
	if(2*k<heap.size() && dist[heap[k]]>dist[heap[2*k]]) son=2*k;
	if(2*k+1<heap.size() && dist[heap[2*k+1]]<dist[heap[2*k]] && dist[heap[k]]>dist[heap[2*k+1]]) son=2*k+1;
	int aux;
	poz[heap[k]]=son;
	poz[heap[son]]=k;
	aux=heap[k];
	heap[k]=heap[son];
	heap[son]=aux;

	if(k!=son) {k=son; sift(k);}
}
void percolate(int k)
{
	if(k>1 && dist[heap[k/2]]>dist[heap[k]])
	{
		int aux;
		poz[heap[k/2]]=k;
		poz[heap[k]]=k/2;
		aux=heap[k/2];
		heap[k/2]=heap[k];
		heap[k]=aux;
		k=k/2;
		percolate(k);
	}
}
void insert(int k)
{
	heap.push_back(k); poz[k]=heap.size()-1;
	percolate(heap.size()-1);
}
void remove(int k)
{
	heap[k]=heap[heap.size()-1]; poz[heap[heap.size()-1]]=1;
	heap.pop_back();
	//if(k>1 && dist[heap[k/2]]>dist[heap[k]]) percolate(k);
	sift(k);
	
}
void dijkstra()
{
    while(heap.size())
    {
        int i,x; x=heap[1];
        //if(x==dest) {break;}
        for(i=0;i<vecini[x].size();i++)
        {
            if(vecini[x][i].second+dist[x]<dist[vecini[x][i].first])
            {
                dist[vecini[x][i].first]=vecini[x][i].second+dist[x];
                percolate(poz[vecini[x][i].first]);
            }
            if(! dist[vecini[x][i].first] && vecini[x][i].first!=sursa)
            {
                dist[vecini[x][i].first]=vecini[x][i].second+dist[x];
                insert(vecini[x][i].first);
            }
        }
       remove(1);
    }
}
int main()
{
    f>>n>>m;
    int i,x,y,l,j;
    for(i=0;i<m;i++)
    {
        f>>x>>y>>l;
        vecini[x].push_back(make_pair(y,l));
        //vecini[y].push_back(make_pair(x,l));
    }
    sursa=1;
	poz[sursa]=1;
	heap.push_back(0);
    heap.push_back(sursa);
    dist[sursa]=0;
    dijkstra();
    for(i=2;i<=n;i++) g<<dist[i]<<' ';
}