#include <vector>
#include <fstream>
#include <queue>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int oo=2000000000;
const int NMAX=50000;
vector < pair <int,int> >G[NMAX+5];
int n,m,p,D[NMAX+5];
struct cmpD{

 bool operator()(int x,int y)
 {
     return D[x] > D[y];
 }
};
priority_queue< int ,vector <int>, cmpD >Q;
void read()
{
   f>>n>>m;
   for(int i=1;i<=m;i++)
   {
       int x,y,z;
       f>>x>>y>>z;
       G[x].push_back(make_pair(y,z));
   }
}
bool InCoada[NMAX+5];
void Dijkstra(int nodSTART)
{
    for(int i=1;i<=n;i++)
    {
        if(i!=1) D[i]=oo;
    }
    Q.push(nodSTART);
    InCoada[nodSTART]=1;
    while(!Q.empty())
    {
        int nodCurent= Q.top();
        Q.pop();
        InCoada[nodCurent]=0;
        for(int j=0;j<(int)G[nodCurent].size();j++)
        {
            int vecin=G[nodCurent][j].first;
            int cost=G[nodCurent][j].second;
            if(D[nodCurent]+cost<D[vecin])
            {
            D[vecin]=D[nodCurent]+cost;
            if(!InCoada[vecin])
            {
                Q.push(vecin);
                InCoada[vecin]=1;
            }
            }
        }
    }
}
void show()
{
    for(int i=2;i<=n;i++)
    {
        if(D[i]==oo) g<<"0"<<' ';
        else g<<D[i]<<' ';
    }
}
int main()
{
    read();
    Dijkstra(1);
    show();
    return 0;
}