#include<fstream>
#include<vector>
#define MAX_V 50000
#define oo 0x3fffffff
using namespace std;

class Graph {
private:
    bool used[MAX_V + 1];
    int dist[MAX_V + 1], n, m;
    vector<pair<int, int>>g[MAX_V + 1];
public:
    void readGraph() {
        int x, y, c;
        ifstream fin("dijkstra.in");
        fin >> n >> m;
        for(int i = 1; i <= m; i++) {
            fin >> x >> y >> c;
            g[x].push_back(make_pair(y, c));
        }
        fin.close();
    }

    void Dijkstra() {
        int dmin, nod, i, j;
        for(i = 1; i <= n; i++) {
            used[i] = 0;
            dist[i] = oo;
        }
        dist[1] = 0;
        for(i = 1; i <= n - 1; i++) {
            nod = 0;
            dmin = oo;
            for(j = 1; j <= n; j++) {
                if(!used[j] && dist[j] < dmin) {
                    dmin = dist[j];
                    nod = j;
                }
            }
            if(nod) {
                used[nod] = 1;
                for(auto x : g[nod])
                    if(dist[x.first] > dist[nod] + x.second)
                        dist[x.first] = dist[nod] + x.second;
            }
        }
    }

    void printDistances() {
        ofstream fout("dijkstra.out");
        for(int i = 2; i <= n; i++)
            if(dist[i] == oo)
                fout << "0 ";
            else fout << dist[i] << " ";
        fout << "\n";
        fout.close();
    }
};

int main(){
    Graph G;
    G.readGraph();
    G.Dijkstra();
    G.printDistances();
    return 0;
}