#include <bits/stdc++.h>
#define N 50000
#define oo 1e9
using namespace std;

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

int n, m;
vector<pair<int, int> > graf[N + 5];
priority_queue<pair<int, int> > q;
int dist_min[N + 5];
bitset<N + 5> viz; /// viz[i] = 1 => am det pt nodul i dist min

void Citire()
{
    fin >> n >> m;
    int nod1, nod2, cost;
    for(int i = 1; i <= m; ++i)
    {
        fin >> nod1 >> nod2 >> cost;
        graf[nod1].push_back({nod2, cost});
    }
}

void Initializare()
{
    for(int i = 1; i <= n; ++i)
        dist_min[i] = oo;
}

void Dijkstra()
{
    dist_min[1] = 0;
    q.push({0, 1});

    while(!q.empty())
    {
        int cost = -q.top().first;
        int nod = q.top().second;
        q.pop();

        if(!viz[nod])
        {
            for(int i = 0; i < graf[nod].size(); ++i)
            {
                int adiacent = graf[nod][i].first;
                int c = graf[nod][i].second;
                if(cost + c < dist_min[adiacent])
                {
                    dist_min[adiacent] = cost + c;
                    q.push({-dist_min[adiacent], adiacent});
                }

            }

            viz[nod] = 1;
        }

    }
}

void Afisare()
{
    for(int i = 2; i <= n; ++i)
    {
        if(dist_min[i] == oo) dist_min[i] = 0;
        fout << dist_min[i] << " ";
    }
}

int main()
{
   Citire();
   fin.close();
   Initializare();
   Dijkstra();
   Afisare();
   fout.close();

    return 0;
}