#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define NMAX 10010
#define INF 0x3f3f3f3f
using namespace std;
ifstream in("dijsktra.in");
ofstream out("dijsktra.out");



struct NodCost {
  int nod, cost;

  bool operator < (const NodCost& other) const {
    return cost > other.cost;
  }
};

int a, b, x, y, z;
vector <NodCost> G[NMAX];
int dist[NMAX];
priority_queue<NodCost> q;
int n;

void dijkstra(int start) {
	memset(dist, INF, sizeof dist);

	dist[start] = 0;
  	q.push({start, 0});
  	while(!q.empty()) {
      int nod = q.top().nod;
      int cost = q.top().cost;
      q.pop();

      //if(cost != dist[nod]) continue;
      for(auto vec : G[nod]) {
        if(dist[vec.nod] > cost + vec.cost) {
          dist[vec.nod] = cost + vec.cost;
          q.push({vec.nod, dist[vec.nod]});
        }
      }
    }
}

int main()
{
    in>>a>>b;
    for(int i=1;i<=b;i++){
        in>>x>>y>>z;
        G[x].push_back({y,z});
    }
    dijkstra(1);
    for(int i=2;i<=a;i++){
        out<<dist[i]<<" ";
    }


}