/// Craciun Catalin
///  Ubuntzei
///   OJI2011
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

// #define DBG 1
#define NMax 2005
#define INF 0xffffff/2

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n,m,k;
long long pathLen = 0;
vector<int> Nodes;
int V[NMax][NMax]; /// Matricea costurilor

void read() {

    f>>n>>m;
   // f>>k;

    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            V[i][j] = INF;
/*
    for (int i=1;i<=k;i++) {
        int x;
        f>>x;
        Nodes.push_back(x);
    }*/
    for (int i=1;i<=m;i++) {
        int x, y, len;
        f>>x>>y>>len;
        V[x][y] = len;
        //V[y][x] = len;
    }

    f.close();
}

int dijkstra(int begin, int end) {

    int d[NMax], father[NMax], k, minim;
    bool ok = true, visited[NMax];

    for (int i=1;i<=n;i++) {
        d[i] = V[begin][i];
        visited[i] = 0;
        father[i] = begin;
    }

    visited[begin] = 1;
    father[begin] = 0;

    while (ok) {
        minim = INF;
        for (int i=1;i<=n;i++) {
            if (!visited[i] && minim > V[begin][i]) {
                minim = V[begin][i];
                k = i;
            }
        }

        if (minim != INF) {
            visited[k] = 1;
            for (int i=1;i<=n;i++) {
                if (!visited[i] && d[i] > d[k] + V[k][i]) {
                    d[i] = d[k]+V[k][i];
                    father[i] = k;
                }
            }
        } else
            ok = false;
    }

    for (int i=2;i<=n;i++)
        if (d[i] == INF)
            g<<0<<' ';
        else
            g<<d[i]<<' ';

    if (d[end] == INF)
        return 0;
    return d[end];
}
/*
void solve() {

    for (unsigned int i=0;i<Nodes.size()-1;i++) {
        pathLen += djkastra(Nodes[i], Nodes[i+1]);
    }
}*/

int main() {

    //Nodes.push_back(1);
    read();
    //Nodes.push_back(n);
    //solve();
    //g<<pathLen<<'\n';
    dijkstra(1,n);
    g.close();

    return 0;
}