#include <fstream>
#include <functional>
#include <vector>
#include <queue>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,x,y,c,i,viz[200010];
long long suma;
priority_queue < pair < int,int > , vector < pair < int,int > > , greater < pair < int,int > > >qu;
vector < pair < int,int > >g[200010];
struct tata
{
    int d,n;
}t[200010];
void apm()
{
    qu.push({0,1});
    while(qu.empty()==0)
    {
        int nod=qu.top().second;
        qu.pop();
        if(viz[nod]==0)
        {
            viz[nod]=1;
            for(int i=0;i<g[nod].size();i++)
            {
                if(viz[g[nod][i].first]==0)
                {
                    if(t[g[nod][i].first].d>g[nod][i].second)
                    {
                        t[g[nod][i].first].d=g[nod][i].second;
                        t[g[nod][i].first].n=nod;
                    }
                    qu.push({t[g[nod][i].first].d,g[nod][i].first});
                }
            }
        }
    }
}
int main()
{

    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        g[x].push_back({y,c});
        g[y].push_back({x,c});
        t[i].n=1;
        if(i!=1)
        t[i].d=2000000000;
    }
    apm();
    for(i=1;i<=n;i++)
        suma+=t[i].d;
    fout<<suma<<'\n'<<n-1<<'\n';
    for(i=2;i<=n;i++)
        fout<<i<<" "<<t[i].n<<'\n';
    return 0;
}