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

struct tip
{
    int nod,cost;
    bool operator<(const tip&other) const
    {
        return cost>other.cost;
    }
};

priority_queue<tip> q;

const int maxN=(2e5)+5;

int n,m,x,y,z;
vector<pair<int,int> > edges,v[maxN];
int dp[maxN],pre[maxN];
const int inf=(1e9);
int sol;
bool seen[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;


    for(int i=1;i<=n;i++)
        q.push({i,dp[i]});

    int nodes=0;
    while(nodes<n)
    {
        int nod=q.top().nod;
        int cost=q.top().cost;

        q.pop();

        if(cost>dp[nod]) continue;
        nodes++;
        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)
            {
                pre[it.first]=nod;
                dp[it.first]=z;
                q.push({it.first,dp[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;
}