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

using namespace std;

const int MAX = 50005;
const int nrMAX = 0x3f3f3f3f;

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);
void solve(int N);

int main()
{
    int N;

    citire(N);
    solve(N);

    return 0;
}

void citire(int &N)
{
     int x,y,l,M;
     fstream f("dijkstra.in",ios::in);
     f>>N>>M;
     do
        {
        f>>x>>y>>l;
        Djk[x].push_back(make_pair(y,l));
        }while(--M);
}

void solve(int N)
{
    ofstream g("dijkstra.out");
    int i;

    memset(Dst,nrMAX,sizeof Dst);

    Dst[1] = 0;
    Q.push(1);

    while(!Q.empty())
        {
         i = Q.top();
         Q.pop();

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

}