#include<fstream>
#include<vector>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
    int noduri;
    int muchii;
    vector<int> adiacenta[100001];
    void Djk()
    {
        int  x, y, cost, nr_noduri, p, q;
        vector <int> costuri[10000], drumuri, h, d, lungime;
        in >> noduri >> muchii;
        drumuri.resize(muchii + 1);
        h.resize(muchii + 1);
        d.resize(muchii + 1);
        lungime.resize(muchii + 1);
        for (int i = 0; i <= muchii; i++)
        {
            drumuri.push_back(0);
            h.push_back(0);
            d.push_back(0);
            lungime.push_back(0);
            adiacenta[i].resize(noduri + 1);
            costuri[i].resize(noduri + 1);
        }
        for (int i = 1; i <= muchii; i++)
        {
            in >> x >> y >> cost;
            adiacenta[x].push_back(y);
            costuri[x].push_back(cost);
            if (i <= noduri)
            {
                drumuri[i] = 100000;
                h[i] = i;
                d[i] = i;
            }
            lungime[x] = adiacenta[x].size();
        }
        drumuri[1] = 0;
        nr_noduri = noduri;
        for (int i = 1; i <= noduri; i++)
        {
            for (int j = 0; j < lungime[h[1]]; j++)
                if (drumuri[h[1]] + costuri[h[1]][j] < drumuri[adiacenta[h[1]][j]])
                {
                    drumuri[adiacenta[h[1]][j]] = drumuri[h[1]] + costuri[h[1]][j];
                    p = d[adiacenta[h[1]][j]];
                    q = 1;
                    while (q == 1 && p > 1)
                    {
                        q = 0;
                        if (drumuri[h[p]] < drumuri[h[p + 1]])
                        {
                            q = 1;
                            swap(h[p], h[p + 1]);
                            swap(d[h[p]], d[h[p + 1]]);
                            p++;
                        }
                    }
                }
            d[h[1]] = nr_noduri;
            h[1] = h[nr_noduri--];
            p = 1;
            while (1)
            {
                y = 0;
                if (nr_noduri >= p * 2 + 1 && drumuri[h[p * 2 + 1]] < drumuri[h[p * 2]])
                    y = 1;
                if (nr_noduri >= p * 2 + y && drumuri[h[p]] > drumuri[h[p * 2 + y]])
                {
                    q = 1;
                    swap(h[p], h[p * 2 + y]);
                    swap(d[h[p]], d[h[p * 2 + y]]);
                    p = p * 2 + y;
                    continue;
                }
                break;
            }
        }
        for (int i = 2; i <= noduri; i++)
        {
            if (drumuri[i] == 100000)
                out << "0 ";
            else
                out << drumuri[i] << " ";
        }
    }
int main()
{
	Djk();
	return 0;
}