#include <fstream>
#include <vector>
#include <set>
#include <utility>
#include <iostream>

const int inf = 2048;

using std::pair;
using std::set;
using std::cout;
using std::vector;
std::ifstream in("dijkstra.in");
std::ofstream out("dijkstra.out");

struct graf
{
    int n, cost;
    graf *next;
};
vector< vector< pair<int,int> > > a;
int N,M;
vector<int> dist,pred;

void read()
{
    int x,y,z;
    for (int i = 0; i < M; ++i) {
        in >> x >> y >> z;
    pair<int, int> p(y, z);
    a[x].push_back(p);
    }
}


int main()
{
    in >> N >> M;
    a.resize(N + 1);
    read();
    dist.resize(N + 1, inf); pred.resize(N + 1);
    dist[1] = 0;


    for (int i = 1; i <= N; ++i)
        for (int j = 0; j < a[i].size(); ++j)
        if ( dist[i] + a[i][j].second < dist[ a[i][j].first ] ) {
            dist[ a[i][j].first ] = dist[i] + a[i][j].second;
            pred[ a[i][j].first ] = i;
        }


    for (int i = 2; i < dist.size(); ++i)
        out << dist[i] << " ";

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