# include <cstdio>
# include <set>
# include <utility>

# define N 200010
# define pb push_back
# define mp make_pair
# define in insert
# define F first
# define S second
# define X (*it).S.F
# define Y (*it).S.S
# define cost (*it).F

using namespace std;

struct solutie
{
    int x,y;
}sol[N];

multiset < pair< int, pair< int , int> > > s;
multiset < pair< int, pair< int , int> > > :: iterator it;
int nr,n,m,i,x,y,C,c;
int r[N],t[N];

int find(int x)
{
    if(t[x]!=x) t[x]=find(t[x]);
    return t[x];
}

void reuneste(int x, int y)
{
    if(r[x]>r[y]) t[y]=x;
    else t[x]=y;
    if(r[x]==r[y]) r[x]++;
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    scanf("%d %d\n", &n, &m);
    for(i=1; i<=m; ++i)
    {
        scanf("%d %d %d\n", &x, &y, &c);
        s.in(mp(c,mp(x,y)));
    }

    for(i=1; i<=n; ++i)
        r[i]=1,t[i]=i;

    for(it=s.begin(); it!=s.end() && nr<n; ++it)
    {
        x=find(X), y=find(Y);
        if(x!=y)
        {
            C+=cost;
            sol[++nr].x=x;
            sol[nr].y=y;
            reuneste(x,y);
        }
    }

    printf("%d\n%d\n", C, n-1);
    for(i=1; i<n; ++i)
        printf("%d %d\n", sol[i].y, sol[i].x);
}