#include<bits/stdc++.h>
#define INF 1e9

using namespace std;

vector<vector<pair<int,int>>> adj;
vector<int> dist;

void dijkstra(int start)
{
  priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

  pq.push({0, start});

  while(!pq.empty())
  {
    pair<int,int> weightNode = pq.top();
    pq.pop();

    int minPathCost = weightNode.first;
    int minPathEnd = weightNode.second;

    if (dist[minPathEnd] != INF)
      continue;

    dist[minPathEnd] = minPathCost;

    for(int i = 0; i < adj[minPathEnd].size(); i++)
    {
      pair<int,int> nextWeightNode = adj[minPathEnd][i];
      int nextWeight = nextWeightNode.first;
      int nextNode = nextWeightNode.second;

      if (dist[nextNode] != INF)
        continue;

      pq.push({dist[minPathEnd] + nextWeight, nextNode});
    }  
  }
}

int main()
{
  ifstream fin("dijkstra.in");
  ofstream fout("dijkstra.out");
  int n, m;
  fin >> n >> m;

  adj.resize(n+5);
  dist.assign(n+5, INF);

  for (int i = 1; i <= m; i++)
  {
    int x,y,z;
    fin >> x >> y >> z;

    adj[x].push_back({z, y}); // weight then node
  }

  dijkstra(1);

  for (int i = 2; i <= n; i++)
  {
    int output = dist[i] == INF ? 0 : dist[i];
    fout << output << " ";
  }
}