#include <iostream>
#include <fstream>
#include <limits.h>
#include <vector>
#include <queue>
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int dist[50001];
int i,j, n,m, a,b,cost, current_dist;
long INFINIT = LONG_MAX;
typedef pair<int, int> nod;
vector<nod>G[50001];

void Dijkstra(int plecare)  {
    for (i=1;i<=n;i++)
        dist[i] = INFINIT;

    dist[plecare] = 0;

    priority_queue< nod, vector<nod>, greater<nod> > pq;//heap
    pq.push(nod(0, plecare));

    while ( !pq.empty() )   {
        nod top = pq.top();
        pq.pop();
        int d = top.first;
        int nod_curent = top.second;

        int listSize;
        for (i=0; i<(int)G[nod_curent].size();++i)   {
            b = G[nod_curent][i].first;
            current_dist = G[nod_curent][i].second;

            if (dist[nod_curent] + current_dist < dist[b])  {
                dist[b] = dist[nod_curent] + current_dist;
                pq.push(nod(dist[b], b));
            }
        }
    }
}

int main()
{
    f>>n>>m;
    for (i=1;i<=m;i++)  {
        f>>a>>b>>cost;
        G[a].push_back(nod(b, cost));
    }
    int plecare = 1;
    Dijkstra(plecare);
for (i=2;i<=n;i++)  {
    if (dist[i]==INFINIT)
        dist[i]=0;
    g<<dist[i]<<" ";
}

    return 0;
}