#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <limits.h>
#include <set>
#define inf INT_MAX-10
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int D[50001], n , m;
vector < pair <int, int> > L[50001];

set <pair<int, int> > h;
//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++)
       if(i!=Start) {D[i]=INT_MAX-10;}


  D[Start]=0;

  h.insert(make_pair(Start, 0));
  while(!h.empty())
  {
      int nod = h.begin()->first;
      int ct = h.begin()->second;
      h.erase(h.begin());

      for(k=0;k<L[nod].size();k++)
      { j=L[nod][k].first;
        c=L[nod][k].second;
        if(D[j]>D[nod]+c)
        {   if (D[j]!= inf)
                    h.erase(h.find(make_pair(j, D[j])));

            D[j]=D[nod]+c;
            //Q.push(make_pair(-D[j],j));
            h.insert(make_pair(j, D[j]));
            //Q.emplace(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;
}