#include <set>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int MAXN=50100;
const int INF=1000000000;
struct muchie {int vf,c;};
int n,m;
int D[MAXN];//distantele
vector<muchie> NU[MAXN];//listele vecinilor impreuna cu costuri
set<pair <int,int> > T;//tetine perechi (distanta, nod)

void citire()
{
    int i,k;
    muchie l;
    fin>>n>>m;
    for(k=1;k<=m;k++)
        {
            fin>>i>>l.vf>>l.c;
            NU[i].push_back(l);
        }
}

void dijkstra()
{
    int i,val, x;
    for(i=2;i<=n;i++) D[i] = INF;
    T.insert(make_pair(0,1));//distanta 0 de la 1 la 1
    while(T.size()>0 )
    {
        val= (*T.begin()).first;//distanta
        x=(*T.begin()).second;//varful
        T.erase(*T.begin());//sterg primul varf
        for(i=0;i<NU[x].size();i++)//parcurg vecinii sai
         if(D[NU[x][i].vf]>val+NU[x][i].c)//daca scade distanta minima
            {
                D[NU[x][i].vf]=val+NU[x][i].c;//actualizez distanta minima
                T.insert(make_pair(D[NU[x][i].vf],NU[x][i].vf));//pun in multime noua pereche (distanta, varf)
            }
    }
}

int main(void)
{
    citire();
    dijkstra();
    for(int i=2;i<=n;i++)
       if(D[i]==INF) fout<<"0 ";
       else fout<<D[i]<<" ";
    fin.close();
    fout.close();
    return 0;
}