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

using namespace std;

const int MAX = 50005;
const int nrMAX = 2147483647;

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

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

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

int Dst[MAX];
bool checked[MAX];

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.empty())
        {
         i = Q.top();
         Q.pop();

         checked[i] = 0;
         for(it = Djk[i].begin();it!=Djk[i].end();++it)
            {
             x = it->first;
             y = it->second;

             if(Dst[i]+y<Dst[x])
                {
                Dst[x] = Dst[i] + y;
                if(checked[i]==0)
                 {
                Q.push(x);
                checked[x]=1;
                 }
                }
            }
        }
    for(i=2;i<=N;++i)
        {
            if(Dst[i]== nrMAX)g<<"0 ";
            else g<<Dst[i]<<" ";
        }

}