#include <cstdio>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

priority_queue<pair<int, int>> Q;
vector<vector<pair<int,int>>> Graph;
vector<int> DP;
int N, M;

void dijkstra(int k)
{
  const int INF = 0x3f3f3f3f;
  int cost;
  DP.resize(N);
  fill(DP.begin(), DP.end(), INF);
  DP[k] = 0;

  Q.push({-0, k});

  while (!Q.empty()) {
    tie(cost, k) = Q.top();
    cost *= -1;
    Q.pop();
   
    if (DP[k] != cost) continue;

    for (auto it: Graph[k])
      if (DP[it.first] > DP[k] + it.second) {
	DP[it.first] = DP[k] + it.second;
	Q.emplace(-DP[it.first], it.first);
      }
  }

  for (int i = 1; i < N; ++i)
    if (DP[i] >= INF)
      printf("0 ");
    else
      printf("%d ", DP[i]);
  
}

int main()
{
  freopen("dijkstra.in", "r", stdin);
  freopen("dijkstra.out", "w", stdout);


  scanf("%d%d", &N, &M);
  Graph.resize(N);  
  for (int i = 0; i < M; ++i) {
    int a,b,c;
    scanf("%d%d%d", &a,&b,&c);
    --a;
    --b;
    Graph[a].emplace_back(b, c);
  }

  dijkstra(0);
  
  return 0;
}