#include <fstream>
#include <algorithm>
#include <vector>
#define NMAX 50002
#define INF 10000000;
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct muchie {int vf,cost;};
struct hip {int cost, nod;} aux2;
vector <muchie> L[NMAX];
vector <hip> Cmin;
void citire();
void initializare();
void dijkstra(int x);
bool compara (hip a, hip b) { return a.cost<b.cost;}
int n,m,Dmin[NMAX];
int main()
{
    citire();
    initializare();
    dijkstra(1);
}
void citire()
{
    int a,b,c,i;
    muchie aux;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        aux.vf=b;aux.cost=c;
        L[a].push_back(aux);
    }
}
void initializare()
{
    int i;
    for(i=1;i<=n;i++) Dmin[i]=INF;
    Dmin[1]=0;
    for(i=0;i<L[1].size();i++)
    {
        Dmin[L[1][i].vf]=L[1][i].cost;
        aux2.cost=L[1][i].cost;
        aux2.nod=L[1][i].vf;
        Cmin.push_back(aux2);
    }
    make_heap(Cmin.begin(),Cmin.end(),compara);
}
void dijkstra(int x)
{
    int i,j,vfmin;
    hip aux;
    while(!Cmin.empty())
    {
        aux=Cmin.front();
        vfmin=aux.nod;
        pop_heap(Cmin.begin(),Cmin.end(),compara);
        Cmin.pop_back();
        for(j=0;j<L[vfmin].size();j++)
            if(Dmin[L[vfmin][j].vf]>Dmin[vfmin]+L[vfmin][j].cost)
            {
                Dmin[L[vfmin][j].vf]=Dmin[vfmin]+L[vfmin][j].cost;
                aux2.nod=L[vfmin][j].vf;
                aux2.cost= Dmin[L[vfmin][j].vf];
                Cmin.push_back(aux2);
                push_heap(Cmin.begin(), Cmin.end(),compara);
            }

    }
   for(i=2;i<=n;i++)
   {
       if (Dmin[i]==10000000)
          fout<<0<<" ";
      else
            fout<<Dmin[i]<<" ";
   }
}