#include <fstream>
#include <queue>
#include <vector>
#include <utility>

#define NMAX 50002
#define INF 1e9

using namespace std;

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

int n, m;
struct varf{int x, c;};
vector<varf>G[NMAX];

priority_queue<pair<int, int>> pq;
long long int dist[NMAX]; //dist[i] = distanta minima de la nodul 1 la nodul i
bool viz[NMAX];

void citire();
void dijkstra();
void afisare();

int main()
{
    citire();
    dijkstra();
    afisare();
    return 0;
}

void citire()
{
 int i, x, y, cost;
 varf aux;
 fin>>n>>m;
 for(i = 1; i <= m; i++)
 {
     fin>>x>>y>>cost;
     aux.x = y; aux.c = cost;
     G[x].push_back(aux);
 }
 for(i = 1; i <= n; i++) dist[i] = INF;
}

void dijkstra()
{
 int i, nod;
 pair<int, int>p;
 pq.push({0, 1}); dist[1] = 0;
 while(!pq.empty())
 {
     do
     {
        p = pq.top(); pq.pop();
     }
     while(viz[p.second]);
     viz[p.second] = 1;
     for(i = 0; i < G[p.second].size(); i++)
     {
        if(dist[G[p.second][i].x] > dist[p.second] + G[p.second][i].c)
        {
            dist[G[p.second][i].x] = dist[p.second] + G[p.second][i].c;
            pq.push({-dist[G[p.second][i].x], G[p.second][i].x});
        }
     }
 }
}

void afisare()
{
 int i;
 for(i = 2; i <= n; i++)
    fout<<dist[i]<<' ';
 fout<<'\n';
}