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

using namespace std;
ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");
int n,m,a,b,c;
int i,j,k,nod,cost;
int COST[270000],VIZ[270000];

vector <pair <int,int> > A[270000];
vector <pair <int,int> > :: iterator it;
queue <int> Q;

void dijkstra(int k)
{
    vector <int> :: iterator it;
   
}
int main()
{
    fi>>n>>m;
    for (i=1;i<=m;i++)
    {
        fi>>a>>b>>c;
        A[a].push_back(make_pair(b,c));
    }
    for (i=2;i<=n;i++)
        COST[i]=100000000;
   
   
    Q.push(1);
   
    while (!Q.empty())
    {
        k=Q.front();
        for (it=A[k].begin();it!=A[k].end();it++)
		{
			nod=(*it).first;
			cost=(*it).second;
			if (COST[nod]>COST[k]+cost)
			{
				COST[nod]=COST[k]+cost;
				Q.push(nod);
			}
		}
		Q.pop();
    }
   
    for (i=2;i<=n;i++)
        if(COST[i]!=100000000)
            fo<<COST[i]<<" ";
        else fo<<0<<" ";
    fi.close();
    fo.close();   
    return 0;
}