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

#define Nmax 50002
#define cost first
#define nod second
#define INF 0x3f3f3f3f

using namespace std;

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

int n, m, i, j, c, viz[Nmax];
vector < pair < int, int > > G[Nmax];
vector < pair < int, int > > :: iterator it;
priority_queue < pair < int, int >, vector < pair < int, int > >, greater < pair < int, int > > > pq;
pair <int, int> aux;

int main()
{
    fin >> n >> m;
    while (fin >> i >> j >> c)
    {
        G[i].push_back(make_pair(c, j));
    }

    pq.push(make_pair(0, 1));

    while (!pq.empty())
    {
        aux = pq.top();
        pq.pop();
        if (!viz[aux.nod])
        {
            viz[aux.nod] = aux.cost;
            for (it = G[aux.nod].begin(); it != G[aux.nod].end(); it ++)
            {
                if (!viz[(*it).nod])
                    pq.push(make_pair(aux.cost + (*it).cost, (*it).nod));
            }
        }
    }

    for (i = 2; i <= n; i ++)
    {
        fout << viz[i] << " ";
    }

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