#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int HIGH = 10000000;
const int LIM_N = 50001;

struct nxt
{
    int n, c;

    nxt(int _n = 0, int _c = 0)
    : n(_n), c(_c) {}

    friend bool operator>(const nxt& p, const nxt& q)
    {
        return p.c > q.c;
    }
};

int N, M, d[LIM_N];
bool viz[LIM_N];
vector<nxt> L[LIM_N];

void dijkstra(int s)
{
    int a = 0;
    priority_queue<nxt, vector<nxt>, greater<nxt>> pq;
    pq.push(nxt(s, 0));

    while(!pq.empty())
    {
        auto [n, c] = pq.top();
        pq.pop();

        if(!viz[n])
        {
            viz[n] = true;

            if(++a == n)
                break;

            for(const auto& [p, q] : L[n])
            {
                int D = c + q;
                if(D < d[p])
                {
                    pq.push(nxt(p, D));   
                    d[p] = D;     
                }
            }
        }
    }
}

void init(int s)
{
    for(int i = 1; i <= N; i++)
        viz[i] = false, d[i] = (i == s ? 0 : HIGH);
}

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

    fin >> N >> M;
    for(int i = 1; i <= M; i++)
    {
        int a, b, c;
        fin >> a >> b >> c;
        L[a].push_back(nxt(b, c));
    }

    init(1);
    dijkstra(1);

    for(int i = 2; i <= N; i++)
        fout << (d[i] >= HIGH ? 0 : d[i]) << ' ';

    return 0;
}