#include <iostream>
#include <fstream>
#include <vector>
#define MAX 50100
#define INF 100000000

using namespace std;

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

struct nod
{
    int y, c;
};

struct heap
{
    int val, poz;
} H[MAX];

vector <nod> G[MAX];
int dis[MAX], n, m, lung;
bool viz[MAX];

void citire()
{
    int x, y, cost;
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        f >> x >> y >> cost;
        G[x].push_back({y,cost});
    }
    for (int i = 2; i <= n; i++)
        dis[i] = INF;

    f.close();
}

void insert_heap(int &lung, int x, int poz)
{
    int tata, fiu, aux;
    lung++;
    fiu = lung;
    tata = lung / 2;
    H[fiu].val = x;
    H[fiu].poz = poz;

    while (tata > 0 && H[tata].val > H[fiu].val)
    {
        swap(H[tata], H[fiu]);
        fiu = tata;
        tata = fiu / 2;
    }
}

int extract_heap(int &lung)
{
    int tata = 1, fiu = 2, x;
    x = H[1].poz;
    H[1].poz = H[lung].poz;
    H[1].val = H[lung].val;
    --lung;
    while (fiu <= lung)
    {
        if (fiu + 1 <= lung)
            if (H[fiu].val > H[fiu + 1].val)
                ++fiu;
        if (H[tata].val > H[fiu].val)
        {
            swap(H[tata], H[fiu]);
            tata = fiu;
            fiu = fiu * 2;
        }
        else
            break;
    }
    return x;
}

void dijkstra(int start)
{
    int i, vecin, cost, minn;
    insert_heap(lung, dis[start], start);
    viz[start] = 1;

    while (lung)
    {
        minn = extract_heap(lung);
        viz[minn] = 0;
        for (i = 0; i < G[minn].size(); i++)
        {
            vecin = G[minn][i].y;
            cost = G[minn][i].c;
            if (dis[vecin] > dis[minn] + cost)
            {
                dis[vecin] = dis[minn] + cost;
                if (viz[vecin] == 0)
                {
                    insert_heap(lung, dis[vecin], vecin);
                    viz[vecin] = 1;
                }
            }
        }
    }
}

void afisare()
{
    for (int i = 2; i <= n; i++)
    {
       if (dis[i] != INF)
        g << dis[i] << " ";
       else
        g << 0 << " ";
    }
    g.close();
}

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