/*#include <bits/stdc++.
h>
#define fr(i, x, y) for(int i=x; i<=y; i++)
#define ii pair<int, int>
#define iii pair<ii, int>
#define fi first
#define se second */
#include <bits/stdc++.h>
#define fr(i, x, y) for(int i=x; i<=y; i++)
#define ii pair<int, int>
#define iii pair<ii, int>
#define fi first
#define se second
const long long MOD = 1000000007;
using namespace std;
vector<iii> Edg;
int parent[100000];
int dd[1000010];
int n, m;
void inp(){
// freopen("simplify.inp", "r", stdin);
// freopen("simplify.out", "w", stdout);
cin>>n>>m;
fr(i, 1, m){
int u, v, w;
cin>>u>>v>>w;
dd[w]++;
Edg.push_back(iii(ii(u, v), w));
}
fr(i, 1, n)parent[i] = i;
}
void make_set(int v) {
parent[v] = v;
}
int find_set(int v) {
if (v == parent[v])
return v;
return find_set(parent[v]);
}
void union_set(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b)
parent[b] = a;
}
bool comp(iii e1, iii e2){
return e1.se <= e2.se;
}
bool them2(iii e1, iii e2)
{ int u1= find_set(e1.fi.fi);
int v1= find_set(e1.fi.se); int parv1 = parent[v1];
if(u1!= v1)
{
union_set(u1,v1);
int u2= find_set(e2.fi.fi);
int v2= find_set(e2.fi.se); //int parv2 = parent[v2];
if(u2 != v2)
{ parent[v1] = parv1;//union_set(u2,v2);
return 1;
}
else { parent[v1] = parv1; return 0; }
}
else return 0;
}
bool them3(iii e1, iii e2,iii e3)
{
int u1= find_set(e1.fi.fi);
int v1= find_set(e1.fi.se); int parv1 = parent[v1];
if(u1!= v1) //u1!= v1
{ union_set(u1,v1);
int u2= find_set(e2.fi.fi);
int v2= find_set(e2.fi.se); int parv2 = parent[v2];
if(u2 != v2)
{
union_set(u2,v2);
int u3= find_set(e3.fi.fi);
int v3= find_set(e3.fi.se); //parv3 = paren[v3]
if(u3 != v3)
{
parent[v2] = parv2;parent[v1] =parv1;
return 1;
}
else {parent[v2] =parv2;parent[v1] =parv1; return 0;}
}
else {parent[v1] =parv1; return 0;}
}
else return 0;
}
void procs()
{
sort(Edg.begin(), Edg.end(), comp);
long long s=0, cnt = 1;
fr(i, 0, m-1)
{
iii e = Edg[i];
int u, v, w;
u = e.fi.fi; v = e.fi.se; w = e.se;
//cout<<u<<" "<<v<<" "<<w<<endl;
if(dd[w]==1)
{
if(find_set(u)!=find_set(v))
{
s+=w;
union_set(u, v);
}
}
if(dd[w]==2)
{
if(them2(Edg[i],Edg[i+1]))
{
s+=Edg[i].se;
union_set(Edg[i].fi.fi, Edg[i].fi.se);
s+=Edg[i+1].se;
union_set(Edg[i+1].fi.fi, Edg[i+1].fi.se);
}
else
{ int nhan=0;
if (find_set(Edg[i].fi.fi) != find_set( Edg[i].fi.se))
nhan++;
if (find_set(Edg[i+1].fi.fi) != find_set( Edg[i+1].fi.se))
nhan++;
if(nhan==2)
{ s+=Edg[i].se;
cnt = cnt*2%MOD;
union_set(Edg[i].fi.fi, Edg[i].fi.se);
}
if((nhan==1)&&(find_set(Edg[i].fi.fi) !=
find_set( Edg[i].fi.se)))
{ s+=Edg[i].se;
union_set(Edg[i].fi.fi, Edg[i].fi.se);
}
if((nhan==1)&&(find_set(Edg[i+1].fi.fi) !=
find_set( Edg[i+1].fi.se)))
{ s+=Edg[i+1].se;
union_set(Edg[i+1].fi.fi, Edg[i+1].fi.se);
}
}
i++;
continue;
if(dd[w]==3)
{
if(them3(Edg[i],Edg[i+1],Edg[i+2]))
{ // cout<<"######## "<<i<<" "<<w<<endl;
s+=Edg[i].se;
union_set(Edg[i].fi.fi, Edg[i].fi.se);
s+=Edg[i+1].se;
union_set(Edg[i+1].fi.fi, Edg[i+1].fi.se);
s+=Edg[i+2].se;
union_set(Edg[i+2].fi.fi, Edg[i+2].fi.se);
}
else
{ int nhan=0;
if( them2(Edg[i],Edg[i+1])) nhan++;
if( them2(Edg[i],Edg[i+2])) {nhan++;}
if( them2(Edg[i+1],Edg[i+2])) nhan++;
if(nhan ==3)
{
s= s+Edg[i].se +Edg[i+1].se;
cnt = cnt*3%MOD;
union_set(Edg[i].fi.fi, Edg[i].fi.se);
union_set(Edg[i+1].fi.fi, Edg[i+1].fi.se);
}
if(nhan ==2)
{
cnt = cnt*2%MOD;
if( them2(Edg[i],Edg[i+1]))
{ union_set(Edg[i].fi.fi, Edg[i].fi.se);
union_set(Edg[i+1].fi.fi, Edg[i+1].fi.se);
s= s+Edg[i].se +Edg[i+1].se;
}
else if( them2(Edg[i],Edg[i+2]))
{ union_set(Edg[i].fi.fi, Edg[i].fi.se);
union_set(Edg[i+2].fi.fi, Edg[i+2].fi.se);
s= s+Edg[i].se +Edg[i+2].se;
}
else
if( them2(Edg[i+1],Edg[i+2]))
{ union_set(Edg[i+1].fi.fi, Edg[i+1].fi.se);
union_set(Edg[i+2].fi.fi, Edg[i+2].fi.se);
s= s+Edg[i+1].se +Edg[i+2].se;
}
}
if(nhan ==1)
{ s= s+Edg[i].se +Edg[i+1].se;
if( them2(Edg[i],Edg[i+1]))
{ union_set(Edg[i].fi.fi, Edg[i].fi.se);
union_set(Edg[i+1].fi.fi, Edg[i+1].fi.se);
}
else if( them2(Edg[i],Edg[i+2]))
{ union_set(Edg[i].fi.fi, Edg[i].fi.se);
union_set(Edg[i+2].fi.fi, Edg[i+2].fi.se);
}
else if( them2(Edg[i+1],Edg[i+2]))
{ union_set(Edg[i+1].fi.fi, Edg[i+1].fi.se);
union_set(Edg[i+2].fi.fi, Edg[i+2].fi.se);
}
}
if(nhan ==0)
{ int nhan=0; int canhthem;
if(find_set(Edg[i].fi.fi) != find_set(Edg[i].fi.se ))
{ nhan++; canhthem =i;
//s= s+Edg[i].se;
}
if(find_set(Edg[i+1].fi.fi) != find_set(Edg[i+1].fi.se ))
{ nhan++; canhthem =i+1;
if(nhan==1)
{//s= s+Edg[i].se;
}
}
if(find_set(Edg[i+2].fi.fi) != find_set(Edg[i+2].fi.se ))
{ nhan++;canhthem =i+2;
if(nhan==1)
{//s= s+Edg[i].se;
}
}
if(nhan>0)
{ cnt = cnt*nhan%MOD;
union_set(Edg[canhthem].fi.fi, Edg[canhthem].fi.se);
s= s+Edg[canhthem].se;
}
}
i =i+2;
continue;
}
}
cout<<s<<" "<<cnt<<endl;
}
void xuly()
{
sort(Edg.begin(), Edg.end(), comp);
long long s=0, cnt = 1;
fr(i, 0, m-1)
{
iii e = Edg[i];
int u, v, w;
u = e.fi.fi; v = e.fi.se; w = e.se;
//cout<<u<<" "<<v<<" "<<w<<endl;
if(find_set(u)!=find_set(v))
{
s+=w;
union_set(u, v);
}
}
cout<< s<<endl;
}
int main()
{ ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
inp();
procs();
//xuly();
//for(int i=0; i<Edg.size(); i++)
// cout<<Edg[i].fi.fi<<" "<<Edg[i].fi.se<<" "<<Edg[i].se<<endl;
return 0;
}
// bài này là simplify nhá, chưa full vì tle á mà mình cũng không rõ lắm, đây là
code mình tham khảo á
