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

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

const int pinf=200000000;
int d[50010], s[50010], t[50010], n, m;
vector<pair<int, int>> edge[50010];
priority_queue<pair<int, int>> pq;

void citire(int n, int m)
{
    int i, j, c, k;
    for(k=1; k<=m; k++)
    {
        fin>>i>>j>>c;
        edge[i].push_back(make_pair(c, j));
    }

    for(i=1;i<=n;i++)
        d[i] = pinf;
}

int main()
{
    fin>>n>>m;
    citire(n,m);

    s[1] = 1;
    d[1] = 0;
    for (auto x : edge[1]) /// for(i=0; i<edge[p].size(); i++)
    {
        /// y = edge[p][i].second; - j
        /// cost = edge[p][i].first; - costul
        d[x.second] = x.first; /// d[y]=cost;
        t[x.second] = 1; /// t[y] = 1;

        pq.push(make_pair(-x.first, x.second)); /// (-cost, y)
    }

    while(!pq.empty())
    {
        //int dx = pq.top().first * -1;
        int cx = pq.top().second; /// nodul actual
        pq.pop();

        if (s[cx] == 0)
        {
            s[cx] = 1;

            //for (i = 0; i < edge[cx].size(); i++)
            for (auto x : edge[cx])
            {
                int nd = x.first; //edge[cx][i].first; - distanta noua
                int nx = x.second; //edge[cx][i].second; - nodul nou

                if (s[nx] == 0)
                {
                    if (d[nx] > d[cx] + nd)
                    {
                        d[nx] = d[cx] + nd;
                        t[nx] = cx;

                        pq.push(make_pair(-d[nx], nx));
                    }
                }
            }
        }
    }

    for(int i=2; i<=n; i++)
    {
        if(d[i]!=pinf)
            fout<<d[i]<<" ";
        else
            fout<<0<<" ";
    }

    return 0;
}