#include <bits/stdc++.h>
#define nmax 50005
#define infinit (1<<30)
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int costuri[nmax], m, n;
vector < pair <int, int> > graph[nmax];
bool in_coada[nmax];

void citire()
{
    int i, j, x;
    pair <int, int> variabila;
    fin >> n >> m;
    for(i = 0; i < m; i++)
        fin >> x >> variabila.first >> variabila.second, graph[x].push_back(variabila);
    for(i = 2; i <= n; i++)
        costuri[i] = infinit;
    costuri[1] = 0;
}

struct compara{
    bool operator()(int x, int y)
    {
        return (costuri[x] > costuri[y]);
    }
};
priority_queue <int, vector <int>, compara> prq;

void dijkstra(int nod)
{
    int vf, vf2;
    unsigned len, i;
    prq.push(nod);
    in_coada[nod] = 1;
    while(!prq.empty())
    {
        vf = prq.top();
        prq.pop();
        in_coada[vf] = 0;
        len = graph[vf].size();
        for(i = 0; i < len; i++)
           if(costuri[graph[vf][i].first] > costuri[vf] + graph[vf][i].second)
           {
               costuri[graph[vf][i].first] = costuri[vf] + graph[vf][i].second;
               if(!in_coada[graph[vf][i].first])
                    in_coada[graph[vf][i].first] = 1, prq.push(graph[vf][i].first);
           }
    }
}

int main()
{
    int i;
    citire();
    dijkstra(1);
    for(i = 2; i <= n; i++)
        if(costuri[i] != infinit)
            fout << costuri[i] << ' ';
        else
            fout << "0 ";
    return 0;
}