#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

struct Muchie {
    int x, y, cost;
    bool operator<(const Muchie& other) const {
        return cost < other.cost;
    }
};

vector<int> adj[100];
vector<Muchie> muchii;
vector<Muchie> muchiiMST;
int p[1000], h[1000];

void init(int n){
    for(int i = 1; i <= n; i++) {
        p[i] = i;
        h[i] = 0;
    }
}

int find(int x){
    while(x!=p[x]){
        x=p[x];
    }
    return x;
}

void unire(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y) return;
    
    if(h[x] < h[y]){ 
        p[x] = y;
    } else {
        if(h[x] > h[y]){
            p[y] = x;
        } else { 
            p[x] = y;
            h[y]++;
        }
}
}



int main(){
    int n, m, sol=0, x, y, c;
    ifstream f("apm.in");
    f>>n>>m;
    
    init(n);  
    for(int i=0; i<m; i++){
        f>>x>>y>>c;
        muchii.push_back({x, y, c});
    }
    f.close();
    

    sort(muchii.begin(), muchii.end());
   
    for(const auto& muchie : muchii){
        if(find(muchie.x) != find(muchie.y)){
            sol += muchie.cost;
            adj[muchie.x].push_back(muchie.y);
            adj[muchie.y].push_back(muchie.x);
            muchiiMST.push_back(muchie);
            unire(muchie.x, muchie.y);
        }
    }
    
    ofstream g("apm.out");
    g << sol << endl;  
    g << muchiiMST.size() << endl;  
    for(const auto& muchie : muchiiMST){
        g << muchie.x << " " << muchie.y << endl;
    }
    g.close();
    
    
    cout << "Lista de adiacenta:" << endl;
    for(int i = 1; i <= n; i++){
        cout << "Nodul " << i << ": ";
        for(int vecin : adj[i]){
            cout << vecin << " ";
        }
        cout << endl;
    }
    
    return 0;
}