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

#define INF 10000

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);
      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]] = 0;
      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];
  }

  void print()
  {
    for(int i=0; i<heap.size(); i++)
    {
      cout << " vertex " << heap[i] << " key " << keys[heap[i]] << " loc " << loc[heap[i]] << endl;
    }
  }

};

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

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

void print_graph(Graph &graph)
{
  for(int i=0; i<graph.size(); i++)
  {
    cout << i << ": ";
    for(int j=0; j<graph[i].size(); j++)
    {
      cout << graph[i][j].first << "(" << graph[i][j].second << ") ";
    }
    cout << endl;
  }
}

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

  MinHeap myheap(50010);

  // initial heap?
  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;
    dist[nextvertex.first] = nextvertex.second;
    int v = nextvertex.first;
    int newkey;
    int oldkey;
    for(int i=0; i<graph[v].size(); i++)
    {

      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;
}