#include<fstream>
#include<vector>
using namespace std;

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

int n, m, heap[50001], d[50001], heapLength;
bool visited[50001];
vector <int> vertex[50001], length[50001];

void down_up(int i)
{
  int x;

  if(d[heap[i]] < d[heap[i/2]])
  {
    x = heap[i];
    heap[i] = heap[i/2];
    heap[i/2] = x;
    down_up(i/2);
  }
}

void up_down(int i)
{
  int x, y;
  if(d[heap[2*i]] < d[heap[2*i + 1]]) x = 2*i;
  else x = 2*i + 1;
  
  if(d[heap[i]] > d[heap[x]] && x < heapLength)
  {
    y = heap[i];
    heap[i] = heap[x];
    heap[x] = y;
    up_down(x);
  }
}

void add_priority(int x)
{
  heapLength++;
  heap[heapLength - 1] = x;
  down_up(heapLength - 1);
}

int extract_priority()
{
  int x;
  x = heap[0];
  heap[0] = heap[heapLength - 1];
  heapLength--;
  up_down(0);
  return x;
}

void initialise()
{
  int i;
  for(i=1; i<=n; i++) d[i] = 50000001;
}

void dijkstra(int current)
{
  int alt, i, next, nextLength, j;
  heap[0] = current;
  heapLength++;
  d[current] = 0;

  while(heapLength)
  {
    current = extract_priority();
    visited[current] = true;
    for(i=0; i<vertex[current].size(); i++)
    {
      next = vertex[current][i];
      nextLength = length[current][i];
      if(!visited[next])
      {
        alt = d[current] + nextLength;
        if(alt < d[next])
        {
          d[next] = alt;
          add_priority(next);
        }
      }
    }
  }
}

int main()
{
  int x, y, z, i;
  in>>n>>m;
  for(i=1; i<=m; i++)
  {
    in>>x>>y>>z;
    vertex[x].push_back(y);
    length[x].push_back(z);
  }

  initialise();
  dijkstra(1);

  for(i=2; i<=n; i++)
    out<<d[i]<<" ";

  return 0;
}