#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> C;

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

    C.push_back(source);

    list<int>::iterator x= C.begin();
    while ( x!= C.end() )
    {
        for (list<edge>::iterator it=Graf[*x].begin(); it!= Graf[*x].end(); it++)
            {
                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;
                    C.push_back(y.v);
                }
            }
        x++;
    }
}

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;
}