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

#define newn G[nod][i]
#define newc C[nod][i]

using namespace std;

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

const int NMAX = 5e4 + 100;
const int oo = 0x3f3f3f3f;

int N, M, DIST[NMAX];
bool viz[NMAX];
vector <int> G[NMAX], C[NMAX];
typedef pair <int, int> node;
priority_queue <node, vector<node>, greater<node> > Q;

void Dijkstra()
{
    for(int i = 2; i <= N; i++)
        DIST[i] = oo;

    Q.push(node(0, 1));
    while(!Q.empty())
    {
        int nod = Q.top().second, dist = Q.top().first; Q.pop();
        viz[nod] = 1;

        for(unsigned i = 0; i < G[nod].size(); i++)
            if(!viz[newn] && DIST[newn] > DIST[nod] + newc)
            {
                DIST[newn] = DIST[nod] + newc;
                Q.push(node(DIST[newn], newn));
            }
    }
}

int main()
{
    fin >> N >> M;
    while(M--)
    {
        int x, y, c;
        fin >> x >> y >> c;
        G[x].push_back(y);
        C[x].push_back(c);
    }

    Dijkstra();
    for(int i = 2; i <= N; i++)
        if(DIST[i] != oo)
            fout << DIST[i] << ' ';
        else fout << "0 ";
    return 0;
}