#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#define MAX 50001
#include <bitset>
#define INF INT_MAX
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n, m, dist[MAX], T[MAX], s[MAX];

bitset < MAX > viz;

vector < pair < int , int > > v[MAX];

priority_queue < pair< int , int > > heap;

void init()
    {
        for(int i=1; i<=n; i++)
            dist[i]=INF;
    }

void read()
    {
        f>>n>>m;
        int x, y, cost;
        for(int i=1; i<=m; i++)
        {
            f>>x>>y>>cost;
            v[x].push_back(make_pair(y, cost));
        }
    }

void djk()
    {
        init();

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

        dist[1]=0;

        while(!heap.empty())
        {
            int node = heap.top().first;

            heap.pop();

            if(viz[node]==0)
            {
                viz[node]=1;
                for(size_t i=0; i<v[node].size(); i++)
                {
                    int p = v[node][i].first;
                    int cost = v[node][i].second;
                    if(dist[p]>dist[node]+cost)
                    {
                        dist[p]=dist[node]+cost;
                        T[p] = node;
                        heap.push(make_pair(p, -dist[p]));
                    }
                }

            }


        }

    }

void afis()
    {
        for(int i=2; i<=n; i++)
            if(dist[i]==INF)
                g<<0<<" ";
            else g<<dist[i]<<" ";
    }

int main()
{
    read();
    djk();
    afis();
    return 0;
}