#include <iostream>
#include <cstdio>
#include <vector>

#define MAXINT 2147483647

using namespace std;

struct Edge
{
  int cost;
  int target;
  Edge(int t, int c)
  {
    cost = c;
    target = t;
  }
  Edge(const Edge& edge)
  {
    (*this).cost = edge.cost;
    (*this).target = edge.target;
  }
};

class EdgeHeap
{
  vector<Edge> m_heap;
public:
  EdgeHeap()
  {
    m_heap.push_back(Edge(0, -1));
  }

  bool empty()
  {
    return m_heap.size() == 1;
  }

  void insert(const Edge& edge)
  {
    int indice = m_heap.size();
    m_heap.push_back(edge);
    while(m_heap[indice >> 1].cost > m_heap[indice].cost)
    {
      Edge aux(m_heap[indice]);
      m_heap[indice] = m_heap[indice >> 1];
      m_heap[indice /= 2] = aux;
    }
  }

  Edge decapitate()
  {
    const Edge result = m_heap[1];
    m_heap[1] = m_heap[m_heap.size() - 1]; // take last element, put it as first
    m_heap.pop_back();
    int indice = 1;
    while((indice << 1) + 1 < m_heap.size() &&
      ((m_heap[indice].cost > m_heap[(indice << 1)].cost || m_heap[indice].cost > m_heap[(indice << 1) + 1].cost)))
    {
      indice = (m_heap[(indice << 1)].cost < m_heap[(indice << 1) + 1].cost) ? ((indice << 1)) : ((indice << 1) + 1);
      const Edge aux(m_heap[indice]);
      m_heap[indice] = m_heap[indice >> 1];
      m_heap[indice >> 1] = aux;
    }
    if((indice << 1) < m_heap.size())
      if(m_heap[indice].cost > m_heap[(indice << 1)].cost)
      {
        indice *= 2;
        const Edge aux(m_heap[indice]);
        m_heap[indice] = m_heap[indice >> 1];
        m_heap[indice >> 1] = aux;
      }
      return result;
  }
};

vector<Edge> edges[50001];

int main()
{
  freopen("dijkstra.in", "r", stdin);
  freopen("dijkstra.out", "w", stdout);
  int n, m;
  scanf("%d", &n);
  scanf("%d", &m);
  for(int i = 1; i <= m; ++i)
  {
    int firstNode, secondNode, cost;
    scanf("%d", &firstNode);
    scanf("%d", &secondNode);
    scanf("%d", &cost);
    edges[firstNode].push_back(Edge(secondNode, cost));
  }

  EdgeHeap priorityQueue;
  for(int i = 0; i < edges[1].size(); ++i)
    priorityQueue.insert(edges[1][i]);
  vector<int> visited(n + 1, 0);
  vector<int> cost(n + 1, MAXINT);
  cost[1] = 0;
  visited[1] = 1;
  while(!priorityQueue.empty())
  {
    Edge nextEdge = priorityQueue.decapitate();
    int nextNode = nextEdge.target;
    if(!visited[nextNode])
    {
      cost[nextNode] = nextEdge.cost;
      visited[nextNode] = 1;
      for(int i = 0; i < edges[nextNode].size(); ++i)
      {
        int targetNode = edges[nextNode][i].target;
        if(!visited[targetNode])
        {
          priorityQueue.insert(Edge(targetNode, cost[nextNode] + edges[nextNode][i].cost));
        }
      }
    }
  }
  for(int i = 2; i <= n; ++i)
  {
    if(cost[i] == MAXINT)
      printf("0 ");
    else
      printf("%d ", cost[i]);
  }
  return 0;
}