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

using namespace std;
vector< pair<int,int> >g[50005];
priority_queue< pair<int,int>,vector< pair<int,int> >  ,greater< pair<int ,int > >   >q;
 int sel[50005];
int d[50005],n,m,i,j;
ifstream in ("dijkstra.in");
ofstream out ("dijkstra.out");
void djk (int pl)
{

    sel[pl]=1;
    d[pl]=0;
    for(  auto i:g[pl] ){q.push(  {i.second,i.first} );d[i.first]=i.second;}


    while(!q.empty()  )
    {

        while( !q.empty()&& sel[ q.top().second ]==1)q.pop();


if(q.empty () )break;

        int    k =q.top().second;

sel[k]=1;

            for(auto  i:g[k])
            {

                   if(   d[ i.first ]   >  d[k]+i.second )
                   {
                       d[i.first ]=d[k]+i.second;

                    q.push( { d[i.first],i.first   }  );


                   }
            }

    }

}


int x,y,c;
int main()
{


    in>>m>>n;
    for(i=1; i<=n; i++)
    {
        in>>x>>y>>c;
        g[x].push_back({y,c} );
    }

    for(i=1; i<=m; i++)d[i]=9999999;
djk(1);
for(i=2;i<=m;i++){if(d[i]==9999999)out<<"0 ";else out<<d[i]<<" ";}


    return 0;
}