#include <fstream>
#include <vector>

using namespace std;

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


struct nod
{
    int v, l;
};


const int N = 50001;
const int INF = 500000001;

int n, m;
int d[N], poz[N];
vector<nod> a[N];

int nh;
int h[N];
void schimba(int nx, int ny);
void adauga(int nx);
void sterge(int i);
void urca(int i);
void coboara(int i);


void schimba(int nx, int ny)
{
    int aux = h[nx];
    h[nx] = h[ny];
    h[ny] = aux;
    poz[h[nx]] = nx;
    poz[h[ny]] = ny;
}

void adauga(int nx)
{
    h[++nh] = nx;
    poz[nx] = nh;
    urca(nh);
}

void sterge(int i)
{
    schimba(i, nh);
    nh--;
    coboara(i);
}

void urca(int i)
{
    while(i >= 2 && d[h[i]] < d[h[i / 2]])
    {
        schimba(i / 2, i);
        i /= 2;
    }
}

void coboara(int i)
{
    int fs = 2 * i, fd = 2 * i + 1, bun = i;

    if(fs <= nh && d[h[fs]] < d[h[bun]])
        bun = fs;
    if(fd <= nh && d[h[fd]] < d[h[bun]])
        bun = fd;

    if(i != bun)
    {
        schimba(i, bun);
        coboara(bun);
    }
}


void citire()
{
    in >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        int na, nb, l;
        in >> na >> nb >> l;
        a[na].push_back((nod){nb, l});
    }
}


void dijkstra(int nx)
{
    for(int i = 1; i <= n; i++)
        d[i] = INF;

    d[nx] = 0;
    poz[nx] = 1;
    adauga(nx);

    while(nh != 0)
    {
        nx = h[1];
        sterge(1);

        for(size_t i = 0; i < a[nx].size(); i++)
        {
            int ny = a[nx][i].v;
            int l = a[nx][i].l;

            if(d[nx] + l < d[ny])
            {
                d[ny] = d[nx] + l;
                if(poz[ny] == 0)
                    adauga(ny);
                else
                    urca(poz[ny]);
            }
        }
    }
}


void afisare()
{
    for(int i = 2; i <= n; i++)
        if(d[i] == INF)
            out << 0 << ' ';
        else
            out << d[i] << ' ';

    out << '\n';
}


int main()
{
    citire();

    nh = 0;
    dijkstra(1);

    afisare();
    return 0;
}