#include <fstream>
#include <vector>
#include <utility>
#include <map>


struct edge
{
    int s,n,w;
};

const int inf = 1e9;
int N,M;
using std::vector;
using std::map;
std::ifstream in("dijkstra.in");
std::ofstream out("dijkstra.out");
vector<int> dist,prec;
vector<edge> a;

void read()
{
    in >> N >> M;
    dist.resize(N+1,inf);
    dist[1] = 0;
    prec.resize(N+1);
    for (int i = 0; i < M; ++i)
    {
        edge temp;
        in >> temp.s >> temp.n >> temp.w;
        a.push_back(temp);
    }
}

int main()
{

    read();
    int k = 1;
    while (k) {
    k = 0;
        for (int j = 0; j < a.size(); ++j)
        if ( dist[ a[j].s ] + a[j].w  < dist[ a[j].n ] )
    {
        dist[ a[j].n ] = dist[ a[j].s ] + a[j].w;
        prec[ a[j].n ] = a[j].s;
        ++k;
    }
    }

    for (int i = 2; i < dist.size(); ++i)
        if ( dist[i] != inf ) out << dist[i] << " ";
        else out << 0 << " ";


    in.close();
    out.close();
    return 0;
}