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

using namespace std;

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

struct tip
{

    int y,cost;

};

const int N = 50005,INF = (1<<30);

vector <tip> v[N];

int n,m,d[N];

bool viz[N];

struct compara

{

    bool operator()(int x,int y)

    {

        return d[x] > d[y];

    }

};

priority_queue <int,vector<int>,compara> q;

void citire()

{

    in>>n>>m;

    for (int i = 1; i <= m; ++i)

    {

        int a = 0,b = 0,c = 0;

        in>>a>>b>>c;

        tip aux;

        aux.y = b;

        aux.cost = c;

        v[a].push_back(aux);

    }

    for (int i = 0; i <= n + 1; ++i)

        d[i] = INF;

}

void dijkstra(int ns)

{

    d[ns] = 0;

    viz[ns] = true;

    q.push(ns);

    while (!q.empty())

    {

        int nod = q.top();

        q.pop();

        viz[nod] = false;

        for (vector<tip>:: iterator it = v[nod].begin(); it != v[nod].end(); ++it)

        {

//int vecin = v[nod][it].y,cost = v[nod][it].cost;

            int vecin = it -> y,cost = it -> cost;

            if (d[nod] + cost < d[vecin])

            {

                d[vecin] = d[nod] + cost;

                if (viz[vecin] == false)

                {

                    q.push(vecin);

                    viz[vecin] = true;

                }

            }

        }

    }

}

void afisare()

{

    for (int i = 2; i <= n; ++i)

        if (d[i] == INF)

            out<<0<<" ";

        else

            out<<d[i]<<" ";

}

int main()

{

    citire();

    dijkstra(1);

    afisare();

    return 0;

}