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

#define INF 10000000

using namespace std;


class MinHeap
{
  vector<int> heap;
  vector<int> keys;
  vector<int> loc;

  void siftup(int what)
  {
    int parent = what / 2;
    if(keys[heap[parent]] > keys[heap[what]])
    {
      swap(heap[parent], heap[what]);
      loc[heap[parent]] = parent;
      loc[heap[what]] = what;
      siftup(parent);
    }
  }


  void siftdown(int where)
  {
    int lft = where * 2;
    int rgt = where * 2 + 1;

    int maxindex = heap.size() -1;

    if(rgt <= maxindex)
    {
      if(keys[heap[lft]] < keys[heap[rgt]])
      {
        if(keys[heap[where]] > keys[heap[lft]])
        {
          swap(heap[where], heap[lft]);
          loc[heap[where]] = where;
          loc[heap[lft]] = lft;
          siftdown(lft);
        }
      }
      else
      {
        if(keys[heap[where]] > keys[heap[rgt]])
        {
          swap(heap[where], heap[rgt]);
          loc[heap[where]] = where;
          loc[heap[rgt]] = rgt;
          siftdown(rgt);
        }
      }
    }
    else if(lft <= maxindex)
    {
      if(keys[heap[where]] > keys[heap[lft]])
      {
        swap(heap[where], heap[lft]);
        loc[heap[where]] = where;
        loc[heap[lft]] = lft;
        siftdown(lft);
      }
    }

  }

  public:
  MinHeap(int n)
  {
    heap.reserve(n);
    keys.resize(n, -1);
    loc.resize(n, -1);
  }

  void insert(int vertex, int key)
  {

    int oldkey = keys[vertex];
    keys[vertex] = key;
    if(loc[vertex] != -1)
    {
      if(oldkey > key)
      {
        siftup(loc[vertex]);
      }
      else
      {
        siftdown(loc[vertex]);
      }
    }
    else
    {
      heap.push_back(vertex);
      loc[vertex] = heap.size()-1;
      siftup(heap.size()-1);
    }
  }

  int showmin()
  {
    return keys[heap[0]];
  }

  pair<int,int> extract()
  {
    int edge, cost;
    if(heap.size()>0)
    {
      cost = keys[heap[0]];
      edge = heap[0];

      keys[heap[0]] = -1;
      loc[heap[0]] = -1;

      if(heap.size() > 2)
      {
        swap(heap[0], heap[heap.size()-1]);
        heap.pop_back();
        siftdown(0);
      }
      else if(heap.size() == 2)
      {
        swap(heap[0], heap[1]);
        loc[heap[0]] = 0;
        heap.pop_back();
      }
      else
      {
        heap.pop_back();
      }
    }
    else
    {
      edge = 0;
      cost = 0;
    }
    return make_pair(edge, cost);
  }

  int showkey(int edge)
  {
    return keys[edge];
  }

};

typedef vector< vector< pair<int, int> > > Graph;

vector<int> dist;
vector<int> explored;

void dij(Graph &graph, int source)
{
  dist[source] = 0;
  int numexplored = 1; // source
  explored[source] = 1;

  MinHeap myheap(50010);

  for(int i=0; i<graph[source].size(); i++)
  {
    myheap.insert(graph[source][i].first, graph[source][i].second);
  }

  while(numexplored < graph.size())
  {
    pair<int, int> nextvertex = myheap.extract();
    if(nextvertex.first == 0) break;
    int v = nextvertex.first;
    dist[v] = nextvertex.second;
    explored[v] = 1;
    int newkey;
    int oldkey;
    for(int i=0; i<graph[v].size(); i++)
    {
      if(explored[graph[v][i].first] == 0)
      {
        oldkey = myheap.showkey(graph[v][i].first);
        if(oldkey == -1)
        {
          oldkey = INF;
        }
        newkey = min(oldkey, dist[v] + graph[v][i].second);
        myheap.insert(graph[v][i].first, newkey);
      }
    }
    numexplored++;
  }

}

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

  int N, M, v1, v2, cost;
  scanf("%d %d", &N, &M);

  Graph graph(N+1, vector< pair<int,int> >());

  dist.resize(N+1, INF);
  explored.resize(N+1);

  for(int i=0; i<M; i++)
  {
    scanf("%d %d %d", &v1, &v2, &cost);
    graph[v1].push_back(make_pair(v2, cost));
  }

  dij(graph, 1);

  for(int i=2; i<=N; i++)
  {
    if(dist[i] == INF) dist[i] = 0;
    printf("%d ", dist[i]);
  }

  return 0;
}