#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define inf 2e9
#define nmax 50001
using namespace std;

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

int n, m;
vector<int> dist(nmax, inf);
vector<bool> visited(nmax, false);
vector<vector<pair<int, int>>> graph(nmax);
priority_queue<pair<int, int>> pq;

void Dijkstra(int node)
{
   dist.resize(n + 1, inf);
   dist[node] = 0;
   pq.push({0, node});
   while (!pq.empty())
   {
      node = pq.top().second;
      pq.pop();
      if (!visited[node])
      {
         visited[node] = true;
         for (auto neighbour : graph[node])
            if (dist[neighbour.second] > dist[node] + neighbour.first)
            {
               dist[neighbour.second] = dist[node] + neighbour.first;
               pq.push({-dist[neighbour.second], neighbour.second});
            }
      }
   }
}

void read()
{
   fin >> n >> m;
   visited.resize(n + 1, false);
   for (int i = 0; i < m; i++)
   {
      int x, y, z;
      fin >> x >> z >> y;
      graph[x].push_back({y, z});
   }
   fin.close();
}

int main()
{
   read();
   Dijkstra(1);
   for (int i = 2; i <= n; i++)
      if (dist[i] == inf)
         fout << 0 << " ";
      else
         fout << dist[i] << " ";
   fout.close();
   return 0;
}