#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 50000;

int h[NMAX + 5], u[NMAX + 5], c[NMAX + 5];

struct edge
{
    int y, p;
};

int h_size;
bool viz[NMAX + 5];

vector <edge> g[NMAX + 5];

void heap_swap(int a, int b)
{
    swap(u[h[a]], u[h[b]]);
    swap(h[a], h[b]);
}

void heap_up(int p)
{
    int f = p / 2;
    while(c[h[p]] < c[h[f]])
    {
        heap_swap(p, f);
        p = p / 2;
        f = f / 2;
    }
}

void heap_down(int p)
{
    int best, l, r;
    while(2 * p <= h_size)
    {
        l = 2 * p;
        best = l;

        r = 2 * p + 1;
        if(r <= h_size && c[h[l]] > c[h[r]])
            best = r;

        if(c[h[p]] > c[h[best]])
            heap_swap(p, best);
        else break;

        p = best;
    }
}

void heap_insert(int x)
{
    ++h_size;
    h[h_size] = x;
    u[x] = h_size;
    heap_up(h_size);
}

void heap_erase(int x)
{
    int p = u[x];

    heap_swap(p, h_size);
    --h_size;

    heap_up(p);
    heap_down(p);
}

void heap_update(int x)
{
    int p = u[x];

    heap_up(p);
}

void dijkstra()
{
    int x, y, p;
    viz[1] = 1;
    c[1] = 0;
    heap_insert(1);

    while(h_size > 0)
    {
        x = h[1];
        heap_erase(x);

        for(int i = 0; i < g[x].size(); i++)
        {
            y = g[x][i].y;
            p = g[x][i].p;

            if(viz[y] == 0)
            {
                viz[y] = 1;
                c[y] = c[x] + p;
                heap_insert(y);
            }
            else if(c[x] + p < c[y])
            {
                c[y] = c[x] + p;
                heap_update(y);
            }
        }
    }
}

int main()
{
    int n, m, x, y, z;
    edge aux;
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y >> z;
        aux.p = z;
        aux.y = y;
        g[x].push_back(aux);
    }

    dijkstra();

    for(int i = 2; i <= n; i++)
        fout << c[i] << " ";

    fin.close();
    fout.close();
    return 0;
}