#include <bits/stdc++.h>
#define dim 200005
#define inf int(1e9)
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,dp[dim],ans,sugardaddy[dim];
bool viz[dim];
struct apm
{
    int node,cost;
    bool operator<(const apm&other) const
    {
        return cost>other.cost;
    }
};
vector <apm> graph[dim],edge;
priority_queue <apm> q;
void Read()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int x,y,cost;
        f>>x>>y>>cost;
        graph[x].push_back({y,cost});
        graph[y].push_back({x,cost});
    }
}
void Solve()
{
    dp[1]=0;
    for(int i=2;i<=n;++i)
        dp[i]=inf;
    int nodes=0;
    q.push({1,0});
    while(nodes<n)
    {
        int node=q.top().node;
        int cost=q.top().cost;
        q.pop();
        if(cost>dp[node])continue;
        viz[node]=1;
        nodes++;
        ans+=cost;
        if(node!=1)
            edge.push_back({sugardaddy[node],node});
        for(int i=0;i<graph[node].size();++i)
        {
            int son=graph[node][i].node;
            int cost1=graph[node][i].cost;
            if(viz[son])continue;
            if(dp[son]>cost1)
            {
                sugardaddy[son]=node;
                dp[son]=cost1;
                q.push({son,cost1});
            }
        }
    }
}
void Write()
{
    g<<ans<<'\n';
    g<<n-1<<'\n';
    for(int i=0;i<n-1;++i)
        g<<edge[i].node<<" "<<edge[i].cost<<"\n";
}
int main()
{
    Read();
    Solve();
    Write();
    return 0;
}