#include <iostream>
#include <cstdio>
#include <map>
using namespace std;

const long MaxN = 100001;

const long MOD 	= 1000003;


struct Edge{
	long a, b;
	long w;
	
	Edge(){}	
	Edge(long _a, long _b, long _w):a(_a), b(_b), w(_w){}
	
	friend bool operator<(const Edge &a, const Edge &b){
		return a.w < b.w;
	}
};


Edge e[MaxN];
long n, m;

long rez;

bool root[MaxN];
long otac[MaxN];


void init_disjoint(){
	for (long i = 0; i < MaxN; i++){
		root[i] = true;
		otac[i] = 1;
	}
}

long group(long x){
	long tmp = x, tmp1;
	while (!root[x]) x = otac[x];
	while (!root[tmp]){
		tmp1 = otac[tmp];
		otac[tmp] = x;
		tmp = tmp1;
	}
	return x;
}

void merge(long _x, long _y){
	long x = group(_x), y = group(_y);
	if (x == y) return;
	
	if (otac[x] > otac[y]){
		otac[x] += otac[y];
		otac[y] = x;
		root[y] = false;
	}
	else{
		otac[y] += otac[x];
		otac[x] = y;
		root[x] = false;
	}
}

void count2(long *a, long *b, long idBr){
	if (idBr == 2) rez *= 2;
}

void count3(long *a, long *b, long idBr){
	if (idBr == 2) rez *= 3;
	else if (idBr == 3){
		if ((a[0] == a[1] && b[0] == b[1]) || (a[0] == a[2] && b[0] == b[2]) || (a[1] == a[2] && b[1] == b[2])) rez *= 2;
		else rez *= 3;
	}
	else if (idBr == 4){
		if ((a[0] == a[1] && b[0] == b[1]) || (a[0] == a[2] && b[0] == b[2]) || (a[1] == a[2] && b[1] == b[2])) rez *= 2;
	}
}

void count4(long *a, long *b, long idBr){
	bool dva = false;
	for (int i = 0; !dva && i < 4; i++) for (int j = i + 1; !dva && j < 4; j++)
		if (a[i] == a[j] && b[i] == b[j])	dva = true;
	
	bool usamljenaGrana = false;
	for (int i = 0; !usamljenaGrana && i < 4; i++){
		usamljenaGrana = true;
		for (int j = 0; usamljenaGrana && j < 4; j++){
			if (i == j) continue;
			if (a[i] == a[j] || a[i] == b[j] || b[i] == a[j] || b[i] == b[j]) usamljenaGrana = false;
		}
	}
	
	int stepen[8];
	for (int i = 0; i < 8; i++) stepen[i] = 0;
	for (int i = 0; i < 4; i++){
		stepen[a[i]-1]++;
		stepen[b[i]-1]++;
	}
	sort(&stepen[0], &stepen[idBr]);
	
	if (idBr == 2) rez *= 4;
	else if (idBr == 3){
		if (stepen[0] == 2 && stepen[1] == 2 && stepen[2] == 4) rez *= 4;
		else if (stepen[0] == 1 && stepen[1] == 3 && stepen[2] == 4) rez *= 3;
		else rez *= 5;
	}
	else if (idBr == 4){
		if (stepen[0] == 2 && stepen[1] == 2 && stepen[2] == 2 && stepen[3] == 2) rez *= 4;
		else if (dva && usamljenaGrana) rez *= 3;
		else{
			if (dva) rez *= 2;
			else if (stepen[0] == 1 && stepen[1] == 2 && stepen[2] == 2 && stepen[3] == 3) rez *= 3;
		}
	}
	else if (idBr == 5){
		if (dva) rez *= 2;
		else if (usamljenaGrana) rez *= 3;
	}
	else if (idBr == 6){
		if (dva) rez *= 2;
	}
}
			

void count(long *paket, long br){
	if (br <= 1) return;
	else{
		map<long, long> mapa;
		long idBr = 1;
		long a[4], b[4];
		
		for (int i = 0; i < br; i++){
			long g1 = group(e[paket[i]].a);
			long g2 = group(e[paket[i]].b);
			if (mapa[g1] == 0) mapa[g1] = idBr++;
			if (mapa[g2] == 0) mapa[g2] = idBr++;
			a[i] = mapa[g1]; b[i] = mapa[g2];
			if (a[i] > b[i]) swap(a[i], b[i]);
		}
		
		idBr--;

		if (br == 4) count4(a, b, idBr);
		else if (br == 3) count3(a, b, idBr);
		else if (br == 2) count2(a, b, idBr);
		
		rez %= MOD;
	}
}
			
void Kruskal(){
	init_disjoint();
	sort(&e[0], &e[m]);
	
	rez = 1; // pretpostavljam da je graf povezan
	
	long last = e[0].w;
	
	long nextGroup[4];
	long br = 0;
	
	nextGroup[br++] = 0;
	
	for (long i = 1; i < m; i++){
		if (e[i].w != last){
			count(nextGroup, br);
			
			for (int j = 0; j < br; j++) merge(e[nextGroup[j]].a, e[nextGroup[j]].b);
	
			br = 0;
			last = e[i].w;
			
		}
		
		long g1 = group(e[i].a);
		long g2 = group(e[i].b);
		
		if (g1 != g2) nextGroup[br++] = i;
	}
	
	count(nextGroup, br);
	for (int j = 0; j < br; j++) merge(e[nextGroup[j]].a, e[nextGroup[j]].b);
}
			
void init(){
	FILE *f;
	f = fopen("stabla.in", "r");
	fscanf(f,"%ld %ld", &n, &m);
	long a, b, w;
	long k = 0;
	for (long i = 0; i < m; i++){
		fscanf(f,"%ld %ld %ld", &a, &b, &w);
		if (a != b)	e[k++] = Edge(a, b, w);
	}
	m = k;
	fclose(f);
}


int main(){
	init();
	Kruskal();
	
	long gr = group(1);
	for (long i = 1; i < n; i++){
		if (group(i) != gr){
			rez = 0;
			break;
		}
	}
	
	FILE *f;
	f = fopen("stabla.out", "w");
	fprintf(f, "%ld\n", rez);
	fclose(f);
	
	return 0;
}