#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
struct edge{
    int nod,cost;
    edge(int nod, int cost):nod(nod),cost(cost){}
    bool operator<(const edge oth) const
    {
        return cost>oth.cost;
    }
};
int n,m,k,r;
vector<edge> G[MAXN];
priority_queue<edge> pq;
int parent[MAXN],key[MAXN];
bool f[MAXN];
int main()
{
    in>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int a,b,c;
        in>>a>>b>>c;
        G[a].push_back(edge(b,c));
        G[b].push_back(edge(a,c));
    }
    fill(begin(parent),end(parent),-1);
    fill(begin(key),end(key),1<<30);
    pq.push(edge(1,0));
    key[1]=0,parent[1]=0;
    while(!pq.empty())
    {
        int u=pq.top().nod;
        pq.pop();
        f[u]=1;
        for(auto i:G[u])
        {
            int v=i.nod,w=i.cost;
            if(!f[v]&&key[v]>w)
            {
                key[v]=w;
                pq.push(edge(v,key[v]));
                parent[v]=u;

            }
        }
    }

    for(int i=2;i<=n;++i)
        if(parent[i]>0)
            ++k,r+=key[i];
    out<<r<<'\n'<<k<<'\n';
    for(int i=2;i<=n;++i)
        if(parent[i]>0)
            out<<i<<' '<<parent[i]<<'\n';
    return 0;
}