#include <fstream>
#include <vector>
//#include <queue>
#define MAX 50005
#define INF 1<<30

using namespace std;

struct data{
    int edge, weight;
} nd;

vector<data> v[MAX];
//queue<int> Queue;

int nodes, edges, distances[MAX];
int initial_point(1);
bool visited[MAX];

void scan();
//void solve();
void efficient();
void write();

int main(){
    scan();
    //solve();
    efficient();
    write();
    return 0;
}

void scan(){
    ifstream fin ("dijkstra.in");
    //char oriented;
    fin >> nodes >> edges;// >> initial_point >> oriented;
    int x, y, z, m = edges;
    while(m--){
        fin >> x >> y >> z;
        nd.edge = y, nd.weight = z;
        v[x].push_back(nd);
        /*if (oriented == 'U'){
            nd.edge = x, nd.weight = z;
            v[y].push_back(nd);
        }*/
    }
    for (int i = 1; i <= nodes; ++i)
        distances[i] = INF;
    fin.close();
}

/*void solve(){
    distances[initial_point] = 0;
    Queue.push(initial_point);

    while(!Queue.empty()){
        int k = Queue.front();
        for (unsigned int i = 0; i < v[k].size(); ++i)
            if (distances[v[k][i].edge] > distances[k] + v[k][i].weight)
                distances[v[k][i].edge] = distances[k] + v[k][i].weight,
                Queue.push(v[k][i].edge);
        Queue.pop();
    }
}*/

void efficient(){
    distances[initial_point] = 0;
    int visCount(0), k, mn;

    while(visCount != edges){
        mn = INF;
        for (int i = 1; i <= edges; ++i)
            if (mn > distances[i] && !visited[i])
                k = i;
        visited[k] = 1;
        ++visCount;

        for (unsigned int i = 0; i < v[k].size(); ++i)
            if (distances[v[k][i].edge] > distances[k] + v[k][i].weight)
                distances[v[k][i].edge] = distances[k] + v[k][i].weight;
    }
}

void write(){
    ofstream fout ("dijkstra.out");
    for (int i = 1; i <= nodes; ++i)
        if (i == initial_point)
            continue;
        //else fout << "Node " << i << ": " << (distances[i] == INF ? -1 : distances[i]) << "\n";
        else fout << (distances[i] == INF ? -1 : distances[i]) << " ";
    fout.close();
}