#include <bits/stdc++.h>
using namespace std;

#define NMAX 50009

class Task {
 public:
    void solve() {
        read_input();
        print_output(get_result());
    }

 private:
    int n;
    int m;
    vector<pair<int, int>> adj[NMAX];

    void read_input() {
        ifstream fin("dijkstra.in");
        fin >> n >> m;
        for (int i = 0; i < m; ++i) {
            int x, y, cost;
            fin >> x >> y >> cost;
            adj[x].push_back({cost, y});
        }
        fin.close();
    }

    vector<int> get_result() {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        q.push({0, 1});
        vector<int> parent(n + 1, 0);
        vector<int> dist(n + 1, 1e9);
        dist[1] = 0;
        while(!q.empty()) {
            int node = q.top().second;
            int cost = q.top().first;
            q.pop();
            if (cost > dist[node])
                continue;
            for (auto &it : adj[node]) {
                int neigh = it.second;
                int edge_cost = it.first;
                if (dist[node] + edge_cost < dist[neigh]) {
                    dist[neigh] = dist[node] + edge_cost;
                    q.push({dist[neigh], neigh});
                    parent[neigh] = node;
                }
            }
        }

        vector<vector<int>> paths(n + 1);
        get_paths(paths, parent);
        for (int i = 1; i <= n; ++i) {
            for (int &j : paths[i])
                cout << j << ' ';
            cout << endl;
        }
        return dist;
    }

    void get_paths(vector<vector<int>> &paths, vector<int> &parent) {
        for (int i = 1; i <= n; ++i)
            path(i, paths, parent);
    }

    void path(int i, vector<vector<int>> &paths, vector<int> &parent) {
        if (!parent[i]) {
            paths[i].push_back(i);
            return;
        }
        if (paths[parent[i]].empty()) {
            path(parent[i], paths, parent);
        }
        paths[i].assign(paths[parent[i]].begin(), paths[parent[i]].end());
        paths[i].push_back(i);
    }

    void print_output(const vector<int> &result) {
        ofstream fout("dijkstra.out");
        for (int i = 2; i <= n; ++i) {
           fout << ((result[i] == 1e9) ? 0 : result[i]) << ' ';
        }
        fout.close();
    }
};

// Please always keep this simple main function!
int main() {
    // Allocate a Task object on heap in order to be able to
    // declare huge static-allocated data structures inside the class.
    Task *task = new Task();
    task->solve();
    delete task;
    return 0;
}