#include<bits/stdc++.h>



using namespace std;



ifstream fin("dijkstra.in");



ofstream gout("dijkstra.out");



const int NMax=50052;



const int Dim=(1<<30);



typedef struct LM{int nod,cost;};



int d[NMax];



int n,m;



vector <int> G[NMax], C[NMax];







typedef struct cmpdst



{



    bool operator() (LM x, LM y)



    {



        return x.cost>y.cost;



    }



};







priority_queue <LM, vector<LM> , cmpdst> q;











void citire()



{   int i,x,y,z;



    fin>>n>>m;



for (i=1;i<=m;i++)



{



    fin>>x>>y>>z;



    G[x].push_back(y);



    C[x].push_back(z);







}







}











void dijkstra(int S)



{   int viz[NMax]={0},i;



    for(i=1;i<=n;i++)



        d[i]=Dim;



    d[S]=0;



    LM aux,aux2;



    aux.cost=0;



    aux.nod=S;



    q.push(aux);



    while(!q.empty())



    {



        aux=q.top();



        q.pop();



        if(viz[aux.nod]==1);



        else



        {



            viz[aux.nod]=1;



            for(i=0;i<G[aux.nod].size();i++)



            {



               int halp;



                halp=G[aux.nod][i];

                if(!viz[halp])



                {if(d[halp]>d[aux.nod]+C[aux.nod][i])



                {



                    d[halp]=d[aux.nod]+C[aux.nod][i];



                    aux2.nod=halp;



                    aux2.cost=d[halp];



                    //if(!viz[aux2.nod])

                    q.push(aux2);







                }

                }



            }



        }







    }



}



void afisare()



{



    int i;



    for(i=2;i<=n;i++)



        if(d[i]!=Dim) gout<<d[i]<<' ';



    else gout<<"0 ";



}







int main()



{



    citire();



    dijkstra(1);



    afisare();



}