/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

package labpa10;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;

/**
 *
 * @author Stef
 */
class nod{
    int id;
    int set;
    ArrayList<nod> neighbors;
    ArrayList<Integer> costs;
    boolean visited;
    
    public nod (int i){
        id=i;
        set=i;
        neighbors=new ArrayList<>();
        costs=new ArrayList<>();
    }
    
    public void reset(){
        visited=false;
    }
}

class muchie{
    nod n1,n2;
    int cost;
    boolean passed;
    public muchie (nod nod1,nod nod2,int c){
        n1=nod1;
        n2=nod2;
        cost=c;
        passed=false;
    }
}

public class p1 {
    /**
     * @param args the command line arguments
     */
    static int[][] max;
    public static int min(int a,int b){
        if (a<b) return a;
        return b;
    }
    public static int maximum(int a,int b){
        if (a>b) return a;
        return b;
    }
    public static void parcurgere(nod sursa,nod crt,int m){
        crt.visited=true;
        for(int i=0;i<crt.neighbors.size();i++){
            if (!crt.neighbors.get(i).visited) {
                parcurgere(sursa,crt.neighbors.get(i),maximum(m,crt.costs.get(i)));
            }
        }
        max[sursa.id][crt.id]=m;
    }
    
    public static void main(String[] args) throws IOException {
        //ArrayList<ArrayList<
        ArrayList<muchie> MuchiiAMA=new ArrayList<>();
        int n,m;
        int a,b,c;
        BufferedReader br = new BufferedReader(new FileReader("graf.in"));
        String line;
        line=br.readLine();
        String[] parts = new String[3];
        parts=line.split(" ");
        n=Integer.valueOf(parts[0]);
        m=Integer.valueOf(parts[1]);
        ArrayList<nod> noduri = new ArrayList<>();
        ArrayList<muchie> muchii = new ArrayList<>();
        for(int i = 0;i < n;i++){
            noduri.add(new nod(i));
        }
        max=new int[n][n];
        ArrayList<Integer> costs=new ArrayList<>();
        for(int i=0;i<m;i++){
            line=br.readLine();
            parts=line.split(" ");
            a=Integer.valueOf(parts[0]);
            b=Integer.valueOf(parts[1]);
            c=Integer.valueOf(parts[2]);
            muchii.add(new muchie(noduri.get(a-1),noduri.get(b-1),c));
            costs.add(c);
            noduri.get(a-1).neighbors.add(noduri.get(b-1));
            noduri.get(a-1).costs.add(c);
            noduri.get(b-1).neighbors.add(noduri.get(a-1));
            noduri.get(b-1).costs.add(c);
        }
        
        Collections.sort(costs);
        ArrayList<muchie> edges = new ArrayList<>();

        for(int i=0;i<m;i++){
            for(int j=0;j<muchii.size();j++){//creez o noua lista luand pe rand costurile ordonate si punand intr-o noua lista toate muchiile dupa aceeasi ordonare
                if (costs.get(i)==muchii.get(j).cost) {
                    edges.add(muchii.get(j));
                    muchii.remove(j);
                    j--;
                }
            }
        }
        int k;
        int[] mem=new int[n];
        int o,p;
        for(int i=0;i<m && MuchiiAMA.size()<noduri.size()-1;i++){
            if (edges.get(i).n1.set!=edges.get(i).n2.set){
                k=min(edges.get(i).n1.set,edges.get(i).n2.set);
                for(int j=0;j<n;j++){
                    mem[j]=noduri.get(j).set;
                }
                o=edges.get(i).n1.set;
                p=edges.get(i).n2.set;
                for(int j=0;j<n;j++){//schimb set-ul tuturor nodurilor care au acelasi set cu n2 sau n1 sa fie acelasi cu minimul dintre ele
                    if (mem[j]==o || mem[j]==p) noduri.get(j).set=k;
                }
                MuchiiAMA.add(edges.get(i));
                edges.get(i).passed=true;
            }
        }
        int sum=0;
        for(int i=0;i<MuchiiAMA.size();i++){
            System.out.println(MuchiiAMA.get(i).n1.id+" "+MuchiiAMA.get(i).n2.id+" "+MuchiiAMA.get(i).cost);
            sum+=MuchiiAMA.get(i).cost;
        }
        System.out.println("\nAMA1: "+sum+"\n");
        
        for(int i=0;i<n;i++){
            noduri.get(i).neighbors=new ArrayList<>();
            noduri.get(i).costs=new ArrayList<>();
        }
        for(int i=0;i<MuchiiAMA.size();i++){//refac informatia din noduri pe baza datelor din MuchiiAMA
            MuchiiAMA.get(i).n1.neighbors.add(MuchiiAMA.get(i).n2);
            MuchiiAMA.get(i).n1.costs.add(MuchiiAMA.get(i).cost);
            MuchiiAMA.get(i).n2.neighbors.add(MuchiiAMA.get(i).n1);
            MuchiiAMA.get(i).n2.costs.add(MuchiiAMA.get(i).cost);
        }
        
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                noduri.get(j).reset();
            }
            parcurgere(noduri.get(i),noduri.get(i),0);
            for(int j=0;j<n;j++){
                System.out.print(max[i][j]+" ");
            }
            System.out.println();
        }
        int min=100000;
        for(int i=0;i<m;i++){
            if (edges.get(i).passed==false){
                if (min>edges.get(i).cost-max[edges.get(i).n1.id][edges.get(i).n2.id] && edges.get(i).cost-max[edges.get(i).n1.id][edges.get(i).n2.id]>0) min=edges.get(i).cost-max[edges.get(i).n1.id][edges.get(i).n2.id];
            }
        }
        System.out.println("\nAMA2: "+(sum+min));
    }
}