#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <queue>
#define NLIM 50001


using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int N,M,a,b,c,R[NLIM];
const int oo = (1 << 30);
bool in[NLIM];

struct comp
{
    bool operator()(int x,int y)
    {
        return R[x]>R[y];
    }
};

vector < pair <int,int> >  v[NLIM];
priority_queue < int , vector <int> , comp> q;

void dijsktra()
{
    for(int i=2;i<=N;++i)
        R[i]=oo;

    q.push(1);
    R[1]=0;
    in[1]=1;

    while(!q.empty())
    {
        int nc=q.top();
        q.pop();
        in[nc]=0;

        for(size_t i=0;i<v[nc].size();++i)
        {
            int vefin=v[nc][i].first;
            int cost=v[nc][i].second;

            if(R[nc]+cost<R[vefin])
            {
                R[vefin]=R[nc]+cost;

                if(!in[vefin])
            {
                in[vefin]=1;
                q.push(vefin);
            }

            }

        }
    }

}

int main()
{
   fin>>N>>M;
   while(M--)
   {
       fin>>a>>b>>c;
       v[a].push_back(make_pair(b,c));
   }

   dijsktra();

   for(int i=2;i<=N;++i)
    if(R[i]!=oo)fout<<R[i]<<" ";
    else fout<<0<<" ";

    return 0;

}