#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <limits.h>
#define inf=INT_MAX-10
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int D[50001], S[50001], n , m;
vector < pair <int, int> > L[50001];
priority_queue <pair <int, int > > Q;
void Citire()
{int i,x,y,c;
    f>>n>>m;
    for(i=1;i<=m;i++)
    { f>>x>>y>>c;
        L[x].push_back(make_pair(y,c));
    }
}
void Dijkstra()
{int i, j, poz, Start,c,k ;
    Start=1;
    for(i=1;i<=n;i++)
       D[i]=INT_MAX-10;
  D[Start]=0;
  S[Start]=1;
     for(k=0;k<L[Start].size();k++)
     { j=L[Start][k].first;
       c=L[Start][k].second;
        Q.push(make_pair(-c,j));
        D[j]=c;
     }
  while(!Q.empty())
  { poz=Q.top().second;
      Q.pop();
      S[poz]=1;
      for(k=0;k<L[poz].size();k++)
      { j=L[poz][k].first;
        c=L[poz][k].second;
        if(S[j]==0&&D[j]>D[poz]+c)
        {   D[j]=D[poz]+c;
            Q.push(make_pair(-D[j],j));
        }
      }
  }
}
int main()
{ int i;
Citire();
Dijkstra();
for(i=2;i<=n;i++)
    if(D[i]!=INT_MAX-10)
    g<<D[i]<<" ";
    else g<<0;
f.close();
g.close();
    return 0;
}