#include<iostream>

#include<vector>

#include<queue>

#include<stack>

#include<algorithm>

#include<stdio.h>

#include<stdlib.h>

using namespace std;

/*

//函数集合声明下，方便查看

void Dijkstra(const denseGraph& dg, int s);

void spfa(const denseGraph& dg, int s);

weightType prim(const denseGraph& dg, int s);

void makeSet(int x);

int findSet(int x);

void unionSet(int x, int y);

weightType kruskal(const denseGraph& dg);

*/

//稠密图，邻接矩阵表示

#define N 1000            //表示顶点数最大值

#define NOEDGE 1000000    //表示无边，用于距离类求解中

typedef double weightType;    //表示带边权的类型

//定义带权边类

struct edge{

    int v, w;

    weightType val;

    edge(int v = -, int w = -, weightType val = NOEDGE) :v(v), w(w), val(val){}

};

//定义稠密图类

struct denseGraph{

    int Vcnt, Ecnt;    //顶点数，边数

    bool dg;    //有向图 ?

    vector< vector<weightType> > adj;    //邻接矩阵

    denseGraph(int v, bool dg = false) :adj(v), Vcnt(v), Ecnt(), dg(dg){

        for (int i = ; i < v; ++i)

            adj[i].assign(v, NOEDGE);

    }

    void insert(edge e){

        int v = e.v, w = e.w;

        weightType val = e.val;

        if (adj[v][w] == NOEDGE) ++Ecnt;

        adj[v][w] = val;

        if (!dg) adj[w][v] = val;

    }

    void show(){

        printf("Vcnt = %d, Ecnt = %d, Directed : %d\n", Vcnt, Ecnt, dg);

        for (int i = ; i < Vcnt; ++i){

            for (int j = ; j < Vcnt-; ++j)

                cout << adj[i][j] << ' ';

            cout << adj[i][Vcnt - ] << endl;

        }

    }

};

//Dijkstra算法

weightType dDijkstra[N];    //存放所有顶点到 s 的最短路径距离

int pDijkstra[N];        //pDijkstra[i],路径存在时，存放节点 i 的前驱，不存在时，-1

void Dijkstra(const denseGraph &dg, int s)

{

    bool visit[N];    //集合 S ,visit[i]=true, i 属于集合 S

    for (int i = ; i < dg.Vcnt; ++i){    //初始化

        visit[i] = false;

        dDijkstra[i] = dg.adj[s][i];

        pDijkstra[i] = dDijkstra[i] == NOEDGE ? - : s;

    }

    visit[s] = true; dDijkstra[s] = ;

    for (int i = ; i < dg.Vcnt - ; ++i){    //dg.Vcnt-1次选点

        int min = NOEDGE;

        int v = ;

        for (int j = ; j < dg.Vcnt; ++j){    //选距离最近点

            if (!visit[j] && dDijkstra[j] < min){

                v = j; min = dDijkstra[j];

            }

        }

        visit[v] = true;

        for (int j = ; j < dg.Vcnt; ++j){        //更新与 v 直接相连的顶点

            if (!visit[j] && min + dg.adj[v][j] < dDijkstra[j]){

                dDijkstra[j] = min + dg.adj[v][j];

                pDijkstra[j] = v;

            }

        }

    }

}

//最短路径 SPFA算法

weightType dSpfa[N];

int pSpfa[N];

void spfa(const denseGraph& dg, int s)

{

    bool visit[N];

    for (int i = ; i < dg.Vcnt; ++i){

        visit[i] = false;

        dSpfa[i] = NOEDGE;

        pSpfa[i] = -;

    }

    dSpfa[s] = ;

    int u;

    queue<int> q;

    q.push(s);

    while (!q.empty()){

        u = q.front(); q.pop();

        for (int i = ; i < dg.Vcnt; ++i){

            if (dSpfa[u] + dg.adj[u][i] < dSpfa[i]){

                dSpfa[i] = dSpfa[u] + dg.adj[u][i];

                pSpfa[i] = u;

                if (!visit[i])

                    q.push(i);

            }

        }

    }

}

//最小生成树 prim

weightType dPrim[N];    //存放所有顶点到 s 的最短路径距离

weightType prim(const denseGraph& dg, int s)

{

    weightType sum = ;

    bool visit[N];

    for (int i = ; i < dg.Vcnt; ++i){    //初始化

        visit[i] = false;

        dPrim[i] = dg.adj[s][i];

    }

    visit[s] = true; dPrim[s] = ;

    for (int i = ; i < dg.Vcnt - ; ++i){

        weightType min = NOEDGE;

        int v = ;

        for (int j = ; j < dg.Vcnt; ++j){    //选点

            if (!visit[j] && dPrim[j] < min){

                v = j; min = dPrim[j];

            }

        }

        sum += min;

        visit[v] = true;

        for (int j = ; j < dg.Vcnt; ++j){

            if (!visit[j] && dg.adj[v][j] < dPrim[j]){

                dPrim[j] = dg.adj[v][j];

            }

        }

    }

    return sum;

}

//并查集实现，点集[0,1,2,3,4,...,n-1]

int parentSet[N];

int rankSet[N];

void makeSet(int x)

{

    parentSet[x] = x;

    rankSet[x] = ;

}

void linkSet(int x, int y)

{

    if (rankSet[x] > rankSet[y])

        parentSet[y] = x;

    else {

        parentSet[x] = y;

        if (rankSet[x] == rankSet[y])

            ++rankSet[y];

    }

}

int findSet(int x)

{

    vector<int> v;

    while (parentSet[x] != x){

        v.push_back(x);

        x = parentSet[x];

    }

    for (int i = ; i < v.size(); ++i)

        parentSet[v[i]] = x;

    return x;

}

void unionSet(int x, int y)

{

    linkSet(findSet(x), findSet(y));

}

//最小生成树 kruskal

bool kruskalComp(const edge& a, const edge& b)

{

    return a.val < b.val;

}

weightType kruskal(const denseGraph& dg)

{

    weightType sum = ;

    edge e;

    vector<edge> ve;

    for (int i = ; i < dg.Vcnt; ++i)

        for (int j = ; j <= i; ++j)

            if (dg.adj[i][j]!=NOEDGE)

                ve.push_back(edge(i, j, dg.adj[i][j]));

    if (dg.dg){

        for (int i = ; i < dg.Vcnt; ++i)

            for (int j = i + ; j < dg.Vcnt; ++j)

                if(dg.adj[i][j]!=NOEDGE)

                    ve.push_back(edge(i, j, dg.adj[i][j]));

    }

    sort(ve.begin(), ve.end(), kruskalComp);

    for (int i = ; i < dg.Vcnt; ++i)

        makeSet(i);

    for (int i = ; i < ve.size(); ++i){

        e = ve[i];

        int x = findSet(e.v);

        int y = findSet(e.w);

        if (x != y){

            unionSet(x, y);

            sum += e.val;

        }

    }

    return sum;

}

/*测试数据

5 6

1 3 2

1 4 2

3 4 3

1 5 12

4 2 34

5 2 24

7 8

1 3 1

1 4 1

3 7 1

7 4 1

7 5 1

6 7 1

5 2 1

6 2 1

*/

int main()

{

    int v, w, val, n, m;

    cin >> n >> m;

    denseGraph dg(n,true);

    while (m--){

        cin >> v >> w >> val;

        dg.insert(edge(v - , w - , val));

    }

    dg.show();

    cout << endl;

    for (int i = ; i < dg.Vcnt; ++i){

        spfa(dg, i);

        Dijkstra(dg, i);

        for (int i = ; i < dg.Vcnt; ++i)

            cout << dSpfa[i] << ' ';

        cout << endl;

        for (int i = ; i < dg.Vcnt; ++i)

            cout << dDijkstra[i] << ' ';

        cout << endl;

        for (int i = ; i < dg.Vcnt; ++i)

            cout << pSpfa[i] << ' ';

        cout << endl;

        for (int i = ; i < dg.Vcnt; ++i)

            cout << pDijkstra[i] << ' ';

        cout << endl << endl;

    }

    for (int i = ; i < dg.Vcnt; ++i)

        cout << prim(dg, i) << endl;

    cout << kruskal(dg) << endl;

}