#include <fstream>
#include <vector>
#include <queue>
#define inf 2147483646
using namespace std;
ifstream d("dijkstra.in");
ofstream o("dijkstra.out");
int i,j,k,m,n,v[50005],x,y,c,ch[50005];
priority_queue <
 pair <int,pair<int,int> >,
 vector <pair<int,pair<int,int> > >,
 greater <pair<int,pair<int,int> > >
> q;
pair <int,pair<int,int> > e;
vector <pair<int,pair<int,int> > > a[50005];
vector <pair<int,pair<int,int> > >::iterator it;
int main()
  {
    d>>n>>m;
    for (i=1;i<=m;i++)
      {
        d>>x>>y>>c;
        a[x].push_back(make_pair(c,make_pair(x,y)));
      };
    for(i=2;i<=n;i++) v[i]=inf;
    ch[1]=1;k++;
    for (it=a[1].begin();it!=a[1].end();++it)
      {
        q.push(*it);
        if(v[(*it).second.second]>v[(*it).second.first]+(*it).first)
          v[(*it).second.second]=v[(*it).second.first]+(*it).first;
      };
    while (k<=n-1)
      {
        e=q.top();
        q.pop();
        if (ch[e.second.second]==0)
          {
            for (it=a[e.second.second].begin();it!=a[e.second.second].end();++it)
              {
                q.push(*it);
                if(v[(*it).second.second]>v[(*it).second.first]+(*it).first)
                 v[(*it).second.second]=v[(*it).second.first]+(*it).first;
              };
            ch[e.second.second]=1;
            k++;
          };
      };
    for (i=2;i<=n;i++) o<<v[i]<<' ';
  }