#include <fstream>
#include <queue>
using namespace std;
ifstream fi ("dijkstra.in");
ofstream fo ("dijkstra.out");
struct nod
{
  int drumuri;
  int drum[100];
  int cost[100];
  long long dist;
} snod[20000],el;
int nr_arc,nr_nod,i,ni,nf,c,el2,d;
struct cmp {
  bool operator()(const nod& a, const nod& b) const {
    return (a.dist > b.dist); // descrescator
  }
};
priority_queue<nod, vector<nod>, cmp> pq;
int main()
{
    fi>>nr_nod>>nr_arc;
    for (i=1;i<=nr_arc;i++)
    {
      fi>>ni>>nf>>c;
      snod[ni].drumuri++;
      snod[ni].drum[snod[ni].drumuri]=nf;
      snod[ni].cost[snod[ni].drumuri]=c;
    }
    for (i=1;i<=nr_nod;i++) snod[i].dist=250000*20000;
    snod[1].dist=0;
    pq.push(snod[1]);
    while (!pq.empty())
    {
      el=pq.top();
      pq.pop();
      for (i=1;i<=el.drumuri;i++)
      {
        el2=el.drum[i];
        d=el.dist+el.cost[i];
        if (d<snod[el2].dist)
        {
          snod[el2].dist=d;
          pq.push(snod[el2]);
        }
      }
    }
    for (i=2;i<=nr_nod;i++) fo<<snod[i].dist<<' ';
    return 0;
}