#include <fstream>
#include <bitset>
#include <vector>
#include <queue>
#define in "bellmanford.in"
#define out "bellmanford.out"
#define N 50001
#define PII pair<int,int>
#define oo 1e7

using namespace std;

ifstream fin(in);
ofstream fout(out);

int n,m,x,y,p;

bitset<N> viz;
vector<PII> v[N];
priority_queue<PII> heap;

int dist[N];

void Dijkstra()
{
    for(int i=1; i<=n; ++i)
        dist[i] = oo;
    dist[1] = 0;

    heap.push(make_pair(0,1)); // lungimea de la nodul prim la nodul 1 este 0

    while(!heap.empty())
    {
        int nod = heap.top().second;
        heap.pop();

        if(viz[nod]) continue;
        viz[nod] = 1;

        for(int i=0; i<v[nod].size(); ++i)
        {
            int p,q;
            p = v[nod][i].first;
            q = v[nod][i].second; // de la nodul *nod* la nodul *i* este drum la nodul *p* cu valoarea q
            if(dist[p] > dist[nod] + q)
            {
                dist[p] = dist[nod] + q;
                heap.push(make_pair(-dist[p],p));
            }
        }
    }

    for(int i=2; i<=n; ++i)
        if(dist[i] == oo)
            dist[i] = 0;
}

int main()
{
    fin>>n>>m;
    while(m--)
    {
        fin>>x>>y>>p;
        v[x].push_back(make_pair(y,p));
    }

    Dijkstra();

    for(int i=2; i<=n; ++i)
        fout<<dist[i]<<" ";

    fin.close(); fout.close();
    return 0;

}