#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <list>
#include <cassert>
#include <queue>
#include <fstream>
using namespace std;

typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<pair<int,int>> VII;
typedef vector<vector<int>> VVI;
typedef vector<vector<pair<int,int>>> VVP;

void Dijkstra(VVP &adjw, int start, VI &dist, VI &prev) {
    int n=adjw.size();
    dist=VI(n,-1); prev=VI(n,-1);
    VI p(n,-1);  // -1=neobiskan, -2=koncan
    p[start]=0;
    while (1) {
        // najmanjsa potencialna razd.
        int x=-1;
        for (int i=0;i<n;i++) if (p[i]>=0) {
            if (x==-1 || p[i]<p[x]) x=i;
        }
        if (x==-1) break;
        // nastavim razdaljo
        dist[x]=p[x]; p[x]=-2;
        // popravim sosescino
        for (auto [y,w] : adjw[x]) {
            int d=dist[x]+w;
            if (p[y]==-1 || (p[y]>=0 && d<p[y])) {
                p[y]=d;
                prev[y]=x;
            }
        }
    }
}

void DijkstraPQ(VVP &adjw, int start, VI &dist, VI &prev) {
    int n=adjw.size();
    dist=VI(n,-1); prev=VI(n,-1);
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    dist[start]=0;
    pq.push({0,start});
    while (!pq.empty()) {
        auto [d,x]=pq.top(); pq.pop();
        if (d!=dist[x]) continue;
        for (auto [y,w] : adjw[x]) {
            int dy=dist[x]+w;
            if (dist[y]==-1 || dy<dist[y]) {
                dist[y]=dy; prev[y]=x;
                pq.push({dy,y});
            }
        }
    }
}

int main() {
    ifstream fin("weighted.txt");
    int n,m;
    fin >> n >> m;
    VVP adjw(n);
    for (int i=0;i<m;i++) {
        int a,b,c;
        fin >> a >> b >> c;
        adjw[a].push_back({b,c});
        adjw[b].push_back({a,c});
    }
    vector<int> dist,prev;
    Dijkstra(adjw,0,dist,prev);
    for (int i=0;i<n;i++) cout << dist[i] << " ";
    cout << endl;
    for (int i=0;i<n;i++) cout << prev[i] << " ";
    cout << endl;

    DijkstraPQ(adjw,0,dist,prev);
    for (int i=0;i<n;i++) cout << dist[i] << " ";
    cout << endl;
    for (int i=0;i<n;i++) cout << prev[i] << " ";
    cout << endl;
    return 0;
}