#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
priority_queue <pair <int,int> > q;
vector <pair <int,int > > v[50001];
int n,m,i,x,y,c,d[50001],di,nod,j;
int main()
{
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
      f>>x>>y>>c;
      v[x].push_back(make_pair(y,c));
    }
    for (i=2;i<=n;i++)
      d[i]=1<<31-1;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
      di=q.top().first;
      nod=q.top().second;
      q.pop();
      for (j=0;j<v[nod].size();j++)
        if (d[v[nod][j].first]>d[nod]+v[nod][j].second)
        d[v[nod][j].first]=d[nod]+v[nod][j].second,q.push(make_pair(-d[v[nod][j].first],v[nod][j].first));
    }
    for (i=2;i<=n;i++)
      if (d[i]==1<<31-1) g<<0<<' ';
      else g<<d[i]<<' ';
    return 0;
}