#include<vector>
#include<cstdio>
#include<algorithm>
#include<set>
#define N_MAX 200010
#define ins insert
#define mp make_pair
#define pb push_back
#define INF 2000000000
using namespace std;
multiset < pair<int,int> > H;
vector < pair<int,int> > G[N_MAX];
vector < pair<int,int> > Sol;
int T[N_MAX],D[N_MAX],Cost_Final;
bool use[N_MAX];
inline void Write_Data()
{
    printf("%d\n%d\n",Cost_Final,Sol.size());
    for (vector < pair<int,int> > :: iterator it=Sol.begin();it!=Sol.end();++it)
        printf("%d %d\n",(*it).first,(*it).second);
}
inline void APM()
{
    while (!H.empty())
    {
        pair <int,int> X=*(H.begin());
        int Cost=X.first, Nod=X.second;
        H.erase(H.begin());
        if (T[Nod]!=0) Sol.pb(mp(T[Nod],Nod));
        use[Nod]=true; Cost_Final+=Cost;
        for (vector < pair<int,int> > :: iterator it=G[Nod].begin();it!=G[Nod].end();++it)
            if ( (*it).second < D[(*it).first] && !use[(*it).first])
                {
                    if (D[(*it).first]!=INF) H.erase(H.find(mp(D[(*it).first],(*it).first)));
                    T[(*it).first]=Nod; D[(*it).first]=(*it).second;
                    H.ins(mp(D[(*it).first],(*it).first));
                }
    }
}
inline void Load_Data()
{
    int N,M,x,y,c;
    scanf("%d%d",&N,&M);
    for (int i=1;i<=M;++i)
        scanf("%d%d%d",&x,&y,&c), G[x].pb(mp(y,c)), G[y].pb(mp(x,c));
    for (int i=1;i<=N;++i) use[i]=false, D[i]=INF;
    H.ins(mp(0,1)); D[1]=0;
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    Load_Data();
    APM();
    Write_Data();
    fclose(stdin);fclose(stdout);
    return 0;
}