#include <fstream>
#include <list>
#include <string.h>
using namespace std;
ifstream f1("dijkstra.in");
ofstream f2("dijkstra.out");
#define MX 50002
#define INF 1006 * MX

struct edge
{
    int v, cost;
    edge();
    edge(int x, int c ) { v=x; cost=c; }
};

int n, m, dist[MX], predecesor[MX];
list<edge> Graf[MX];

void Bellman_Ford(int source)
{
    list<int> l1, l2, *C= &l1, *Urm= &l2;

    memset(dist, INF, sizeof(dist) );
    dist[source]= 0;

    C->push_back(source);

    while ( !C->empty() )
    {
        while ( !C->empty() )
        {
            int x= *C->begin();
            C->pop_front();

            for (list<edge>::iterator it=Graf[x].begin(); it!= Graf[x].end();)
            {
                edge y= edge(*it);
                if ( dist[x] + y.cost < dist[ y.v ] )
                {
                    dist[ y.v ]= dist[x]+ y.cost;   // visit my neighbour
                    predecesor[ y.v ]= x;
                    Urm->push_back(y.v);
                    it++;
                }
                else
                    it= Graf[x].erase(it);      // if my neighbour does not need me, our relationship ends
            }

        }
        swap(C, Urm);
    }
}

int main()
{
    int i, x, y, c;
    f1>>n>>m;

    for (i=1; i<=m; i++)
    {
        f1>>x>>y>>c;
        edge e(y,c);
        Graf[x].push_back(e);
    }

    Bellman_Ford(1);

    for (i=2; i<=n; i++)
        if ( dist[i] < INF )
            f2<< dist[i]<<" ";
        else f2<<"0 ";

    f2.close();
    return 0;
}