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

using namespace std;

const int NMAX = 50010;

typedef pair<int,int> pi;
priority_queue<pi, vector<pi>, greater<pi> > pq; //perechi cost - destinatie
int N,M, dist[NMAX];
vector<pair<int,int>> G[NMAX];
bool viz[NMAX];




void Dijkstra(int src)
{
    for(int i=1;i<=N;i++)
        if(i!=src)
        {

            dist[i] = NMAX;
            viz[i] = false;
        }


    dist[src] = 0;
    pq.push(make_pair(0,src));

    while(!pq.empty())
    {
        pair<int,int> aux = pq.top();
        pq.pop();

        int nod = aux.second;
        //cout<<viz[nod];
        if(viz[nod])
        {
            continue;
        }


        viz[nod] = true;
        for(auto m: G[nod])  //perechi destinatie - cost
        {
            int next = m.first;
            int cost = m.second;
            if(dist[next]>dist[nod]+cost)
            {
                dist[next] = dist[nod] + cost;
                pq.push(make_pair(dist[next],next));
            }

        }
    }

}
int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>N>>M;
    int s,d,c;
    for(int i=0;i<M;i++)
    {
        f>>s>>d>>c;
        G[s].push_back(make_pair(d,c));
    }

    Dijkstra(1);
    for(int i=2;i<=N;i++)
        if(dist[i] == NMAX)
            g<<0<<" ";
        else
            g<<dist[i]<<" ";



    return 0;
}