#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

int dMax[50001];

struct cell {
  int node, cost;
};

struct minHeap {
  bool operator() (cell a, cell b) {
    if (a.cost > b.cost)
      return 0;
    return 1;
  }
};

vector<cell> graf[50001];
vector<cell>::iterator it;
priority_queue<cell, vector<cell>, minHeap> heap;

int N, M;

void init() {
  for (int i = 0; i <= N; i++)
    dMax[i] = INT_MAX;
}

void dijkstra(int S) {
  heap.push((cell){S, 0});
  init();
  dMax[S] = 0;
  while (!heap.empty()) {
    cell curr = heap.top();
    int currCost = curr.cost;
    int currNode = curr.node;
    heap.pop();
    if (dMax[currNode] == currCost) {
      for (it = graf[currNode].begin(); it != graf[currNode].end(); it++)
        if (dMax[it->node] > currCost + it->cost) {
          dMax[it->node] = currCost + it->cost;
          heap.push((cell){it->node, dMax[it->node]});
        }
    }
  }
}
int info = 1;

ifstream fin(info == 0 ? "date.in" : "dijkstra.in");
ofstream fout(info == 0 ? "date.out" : "dijkstra.out");

int main()
{
  int x, y, c;

  fin>>N>>M;

  for (int i = 1; i <= M; i++) {
    fin>>x>>y>>c;
    graf[x].push_back((cell){y, c});
  }

  dijkstra(1);

  for (int i = 2; i <= N; i++)
    fout<<dMax[i]<<" ";

  return 0;
}