#define FN "test"

#include<cstdio>
#include<cctype>
#include<iostream>
#include<fstream>
#include<functional>
#include<utility>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<set>
#include<complex>
#include<cstring>
#include<string>
#include<cassert>
#include<iomanip>


using namespace std;

typedef long long LL;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(n) (n).begin(), (n).end()
#define EPS 1e-9
#define INF 1e9
#define forn(i, n) for(int i = 0; i < (n); ++i)
#define forab(i, a, b) for(int i = a; (i) < (b); ++(i))
#define forba(i, b, a) for(int i = b-1; i >= (a); --i)
#define forit(i, v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)

int main(){
#ifdef FN
    freopen(FN".in", "r", stdin);
    freopen(FN".out", "w", stdout);
#endif
    int n, m;
    scanf("%d%d", &n, &m);
    vector < vector < pair<int,int> > > g (n);

    forn(i, m){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a-1].pb(mp(b-1, c));
    }

    int s = 0;
    vector<int> d (n, INF),  p (n, 0);
    d[s] = 0;
    p[s] = 0;
    vector<char> u (n);
    for (int i=0; i<n; ++i) {
        int v = -1;
        for (int j=0; j<n; ++j)
            if (!u[j] && (v == -1 || d[j] < d[v]))
                v = j;
        if (d[v] == INF)
            break;
        u[v] = 1;

        for (size_t j=0; j<g[v].size(); ++j) {
            int to = g[v][j].first,
                len = g[v][j].second;
            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
                p[to] = v;
            }
        }
        forn(i, n){
            printf("%d ", i);
        }
        puts("");
        forn(i, n){
            printf("%d ", d[i]);
        }
        puts("");
        forn(i, n){
            printf("%d ", p[i]);
        }
        puts("");
        puts("");
    }
    forn(i, n+1){
        printf("%d ", i);
    }
    puts("");
    forn(i, n+1){
        if(i==0){
            printf("d ");
        } else
        printf("%d ", d[i-1]);
    }
    puts("");
    forn(i, n+1){
        if(i==0){
            printf("p ");
        } else
        printf("%d ", p[i-1]);
    }
    puts("");
}