/**APM-Prim**/
#include<bits/stdc++.h>
using namespace std;

const int maxN=(2e5)+5;
int dp[maxN],pre[maxN];

set<pair<int,int> > q;




int n,m,x,y,z;
vector<pair<int,int> > edges,v[maxN];

const int inf=(1e9);
int sol;
bool seen[maxN],inSet[maxN];


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


    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);

        v[x].push_back(make_pair(y,z));
        v[y].push_back(make_pair(x,z));
    }

    dp[1]=0;

    for(int i=2;i<=n;i++)
        dp[i]=inf;


    q.insert(make_pair(0,1));
    inSet[1]=1;

    int nodes=0;
    while(!q.empty())
    {
        int nod=(*q.begin()).second;
        int cost=dp[nod];

        q.erase(q.begin());

        seen[nod]=1;
        sol+=cost;
        if(nod!=1)
            edges.push_back(make_pair(pre[nod],nod));

        for(auto it:v[nod])
        {
            int z=it.second;
            if(seen[it.first]) continue;
            if(dp[it.first]>z)
            {
                if(dp[it.first]!=inf) q.erase(q.find(make_pair(dp[it.first],it.first)));
                pre[it.first]=nod;
                dp[it.first]=z;
                q.insert(make_pair(dp[it.first],it.first));

            }
        }
    }

    printf("%d\n",sol);
    printf("%d\n",n-1);
    for(auto it:edges)
        printf("%d %d\n",it.first,it.second);

    return 0;
}