#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
struct edge{
    int x,y,c;
    edge(int x=0,int y=0,int c=0):x(x),y(y),c(c){}
    bool operator<(const edge oth)
    {
        return c<oth.c;
    }
};
int n,m,ans,GR[MAXN],ord[MAXN];
vector<edge> G,sol;
void makeSet(int x)
{
    GR[x]=x;
    ord[x]=0;
}
int findSet(int x)
{
    if(x!=GR[x])
        GR[x]=findSet(GR[x]);
    return GR[x];
}
void unionSet(int x, int y)
{
    int px=findSet(x),py=findSet(y);
    if(ord[px]>ord[py])
        GR[py]=px;
    else
        GR[px]=py;
    if(ord[px]==ord[py])
        ord[py]=ord[py]+1;

}

int main()
{
    in>>n>>m;
    G.resize(m+1);
    for(int i=1;i<=m;++i)
        in>>G[i].x>>G[i].y>>G[i].c;
    for(int i=1;i<=n;++i)
        makeSet(i);
    sort(G.begin(),G.end());
    for(edge i : G)
    {
        if(findSet(i.x)!=findSet(i.y))
           {
               ans+=i.c;
               unionSet(i.x,i.y);
               sol.push_back(i);
           }
    }
    out<<ans<<'\n'<<sol.size()<<'\n';
    for(edge i: G)
        out<<i.x<<' '<<i.y<<'\n';
    return 0;
}