# include <cstdio>
# include <vector>
# include <queue>

using namespace std;

FILE *f = freopen("apm.in", "r", stdin);
FILE *g = freopen("apm.out", "w", stdout);

const int N_MAX = 200010;

int n, m;
int total = 0;
int curent;

bool viz[N_MAX];

struct muchie{
    int start;
    int capat;
    int cost;

    muchie (int a, int b, int c){
        this -> start = a;
        this -> capat = b;
        this -> cost = c;
    }

    const bool operator < (const muchie &other) const{
        return this->cost > other.cost;
    }
};

struct vecin{
    int capat;
    int cost;

    vecin (int &a, int &b){
        this -> capat = a;
        this -> cost = b;
    }
};

vector <vecin> G[N_MAX];
priority_queue <muchie> candidati;
vector <pair <int, int> > rez;

void read(){
    scanf("%d %d", &n, &m);

    for (int i=1; i<=m; i++){

        int x, y, c;

        scanf("%d %d %d", &x, &y, &c);

        G[x].push_back(vecin(y, c));
        G[y].push_back(vecin(x, c));
    }
}

void solve(){

    for (vecin M : G[1]){
        candidati.push(muchie(1, M.capat, M.cost));
    }

    viz[1] = true;

    while (!candidati.empty()){
        muchie M = candidati.top();
        candidati.pop();

        if (!viz[M.start] || !viz[M.capat]){
            if (!viz[M.start])
                curent = M.start;
            else
                curent=  M.capat;

            total += M.cost;
            rez.push_back(make_pair(M.start, M.capat));
            viz[curent] = true;

            for (vecin i : G[curent]){
                if (!viz[i.capat]){
                    candidati.push(muchie(curent, i.capat, i.cost));
                }
            }
        }
    }
}

void write(){
    printf("%d\n%d\n", total, rez.size());

    for (pair <int, int> p : rez){
        printf("%d %d\n", p.first, p.second);
    }
}

int main(){
    read();
    solve();
    write();
    return 0;
}