Odrediti broj minimalnih pokrivajućih stabala datog povezanog težinskog grafa u kome se ni jedna težina grane ne ponavlja više od 4 puta.

Ulaz:

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu ulaza su zapisani brojevi N i M(1 ≤ N,M ≤ 5x10⁴), broj čvorova i broj grana datoggrafa. U svakom od narednih M redova zapisana su tri cela brojaA, B i W (1 ≤ A,B ≤ N, 1 ≤ W ≤ 2³⁰), kojioznačavaju da između čvorova A i B postoji grana težine W.

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz) U izlaznu datoteku ispisati ostatak traženogbroja minimalnih pokrivajućih stabala datog grafa koji sedobija pri deljenju sa 1000003.

Primer 1:

3 4
1 2 6
1 2 6
2 3 6
3 1 6
3 3 8

5

Objašnjenje.

Sve grane su iste težine, između čvorova 1 i 2 postoje dvegrane, a postoji i grana kojoj su oba kraja u čvoru 3.

Primer 2:

6 8
1 2 1
2 3 2
3 4 3
4 5 3
5 6 2
6 1 1
2 6 1
3 5 3

6