#include <fstream>
#include <vector>
#include <set>
#define inf 1<<24
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int main()
{
    int n,m;
    f>>n>>m;

    vector < vector < pair <int, int > > > Graph(n+1);
    vector <int> d(n+1,inf), viz(n+1,0), tata(n+1,0);
    set < pair <int, int > > S;

    for (int i=1;i<=m;i++)
    {
        int x,y,cost;
        f>>x>>y>>cost;
        Graph[x].push_back({cost,y});
        Graph[y].push_back({cost,x});
    }

    d[1]=0;
    S.insert({0,1});
    while (!S.empty())
    {
        int nod=S.begin()->second;
        S.erase(S.begin());
        viz[nod]=1;
        for (auto i:Graph[nod])
        {
            if (viz[i.second]==0 && i.first<=d[i.second])
            {
                d[i.second]=i.first;
                S.insert({d[i.second],i.second});
                tata[i.second]=nod;
            }
        }
    }
    int cost=0;
    for (int i=1;i<=n;i++)
    {
        cost+=d[i];
    }
    g<<cost<<'\n'<<n-1<<'\n';
    for (int i=2;i<=n;i++)
    {
        g<<i<<' '<<tata[i]<<'\n';
    }
    return 0;
}