#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
#include <queue>

using namespace std;

const int MAX = 50002;
const int nrMAX = 2147483647;

vector<pair<int,int> > Djk[MAX], h;
vector<pair<int,int> >::iterator it;

struct comparator
{
  bool operator()(int a,int b)
  {
  return a>b;
  }
};

priority_queue<int,vector<int>,comparator> Q;

int Size[MAX],S[MAX],Dst[MAX];
bool checked[MAX];
pair<int,int> MIN;

void citire(int &N,int &M);
void solve(int N,int M);

int main()
{
    int N, M;

    citire(N,M);
    solve(N,M);

    return 0;
}

void citire(int &N,int &M)
{
     int i,x,y,l;
     fstream f("dijkstra.in",ios::in);
     f>>N>>M;
     for(i=1;i<=M;++i)
        {
        f>>x>>y>>l;
        Djk[x].push_back(make_pair(y,l));
        }
}

void solve(int N,int M)
{
    ofstream g("dijkstra.out");
    int i,x,y;
    for(i=2;i<=N;++i)
        {
        Dst[i]= nrMAX;
        }
    Q.push(1);

    while(Q.size())
        {
         i = Q.top();
         Q.pop();

         checked[i] = 1;
         MIN.first = nrMAX;
         for(it = Djk[i].begin();it!=Djk[i].end();++it)
            {
             x = it->first;
             y = it->second;
             if(Dst[i]+y<Dst[x] && checked[x]==0)
                {
                Dst[x] = Dst[i] + y;
                Q.push(x);
                }
            }
        }
    for(i=2;i<=N;++i)
        {
            if(Dst[i]== nrMAX)g<<0<<" ";
            else g<<Dst[i]<<" ";
        }

}