#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

#define Nmax 50005
#define oo 2e10 - 1

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n, m;
int d[Nmax];
bool inCoada[Nmax];
vector < pair < int, int > > g[Nmax];

struct compara
{
  bool operator()(int x, int y)
  {
    return d[x] > d[y];
  }
};


priority_queue < int, vector < int >, compara > coada;

void citire()
{
  int x, y, z;
  fin >> n >> m;
  for (int i = 0; i < m; i ++)
  {
    fin >> x >> y >> z;
    g[x].push_back(make_pair(y, z));
  }
}

void dijkstra(int ns)
{
  for (int i = 1; i <= n; i ++)
    d[i] = oo;
    
  d[ns] = 0;
  inCoada[ns] = true;
  coada.push(ns);
  
  while (!coada.empty())
  {
    int nc = coada.top();
    coada.pop();
    inCoada[nc] = false;
    
    for (size_t i = 0; i < g[nc].size(); i ++)
    {
      int vec = g[nc][i].first;
      int cost = g[nc][i].second;
      
      if (d[nc] + cost < d[vec])
      {
        d[vec] = d[nc] + cost;
        coada.push(vec);
      }
    }
  }
}

void afisare()
{
  for (int i = 2; i <= n; i ++)
    fout << (d[i] != oo ? d[i] : 0) << " ";
  fout << "\n";
}

int main()
{
  citire();
  dijkstra(1);
  afisare();
}