시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 69 11 11 23.404%

문제

가중치가 있고, 연결되어있는 멀티 그래프 (connected weighted multigraph)가 주어졌을 때, 최소 스패닝 트리의 수를 구하는 프로그램을 작성하시오.

멀티 그래프는 루프(자기 자신으로 향하는 간선)이 있을 수 있고, 두 정점 사이에 간선이 여러 개 있을 수도 있다.

입력으로 주어지는 그래프에서 가중치가 같은 간선은 최대 4번 등장한다.

입력

첫째 줄에 정점의 수 N과 간선의 수 M이 주어진다. (1 ≤ N ≤ 5×104, 1 ≤ M ≤ 105) 정점은 1번부터 N번까지 번호가 매겨져 있다. 다음 M개 줄에는 세 정수 a, b, w가 주어지며, 공백으로 구분되어져 있다. (1 ≤ a, b ≤ N, 1 ≤ w ≤ 230) 이 뜻은 a와 b를 연결하는 간선의 가중치가 w라는 뜻이다.

출력

첫째 줄에 최소 스패닝 트리의 개수를 1000003로 나눈 나머지를 출력한다.

예제 입력 1

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

예제 출력 1

5
W3sicHJvYmxlbV9pZCI6Ijc2MjciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyYTRcdWQzMjhcdWIyZGQgXHVkMmI4XHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWFjMDBcdWM5MTFcdWNlNThcdWFjMDAgXHVjNzg4XHVhY2UwLCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjRcdWM3ODhcdWIyOTQgXHViYTQwXHVkMmYwIFx1YWRmOFx1Yjc5OFx1ZDUwNCAoY29ubmVjdGVkIHdlaWdodGVkIG11bHRpZ3JhcGgpXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Y2Q1Y1x1YzE4YyBcdWMyYTRcdWQzMjhcdWIyZGQgXHVkMmI4XHViOWFjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHViYTQwXHVkMmYwIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YjI5NCBcdWI4ZThcdWQ1MDQoXHVjNzkwXHVhZTMwIFx1Yzc5MFx1YzJlMFx1YzczY1x1Yjg1YyBcdWQ1YTVcdWQ1NThcdWIyOTQgXHVhYzA0XHVjMTIwKVx1Yzc3NCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHViNDUwIFx1YzgxNVx1YzgxMCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVhYzA0XHVjMTIwXHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMWMgXHVjNzg4XHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVhZGY4XHViNzk4XHVkNTA0XHVjNWQwXHVjMTFjIFx1YWMwMFx1YzkxMVx1Y2U1OFx1YWMwMCBcdWFjMTlcdWM3NDAgXHVhYzA0XHVjMTIwXHVjNzQwIFx1Y2Q1Y1x1YjMwMCA0XHViYzg4IFx1YjRmMVx1YzdhNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjODEwXHVjNzU4IFx1YzIxOCBOXHVhY2ZjIFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDUmdGltZXM7MTA8c3VwPjQ8XC9zdXA+LCAxICZsZTsgTSAmbGU7IDEwPHN1cD41PFwvc3VwPikgXHVjODE1XHVjODEwXHVjNzQwIDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzEzOCBcdWM4MTVcdWMyMTggYSwgYiwgd1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiAoMSAmbGU7IGEsIGIgJmxlOyBOLCAxICZsZTsgdyAmbGU7IDI8c3VwPjMwPFwvc3VwPikgXHVjNzc0IFx1YjczYlx1Yzc0MCBhXHVjNjQwIGJcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNThcdWFjMDAgd1x1Yjc3Y1x1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNkNWNcdWMxOGMgXHVjMmE0XHVkMzI4XHViMmRkIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgMTAwMDAwM1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI3NjI3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3Bhbm5pbmcgVHJlZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkNvdW50IHRoZSBudW1iZXIgb2YgbWluaW11bS13ZWlnaHQgc3Bhbm5pbmcgdHJlZXMgb2YgYSBjb25uZWN0ZWQgd2VpZ2h0ZWQgbXVsdGlncmFwaCAodGhlcmUgY2FuIGJlIHNlbGYtbG9vcHMsIGFzIHdlbGwgYXMgbXVsdGlwbGUgZWRnZXMgYmV0d2VlbiBhbnkgdHdvIHZlcnRpY2VzKS4gSW4gdGhlIGlucHV0IGdyYXBoLCBubyBlZGdlIHdlaWdodCBhcHBlYXJzIG1vcmUgdGhhbiA0IHRpbWVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgTiBhbmQgTSBzZXBhcmF0ZWQgYnkgYSBzcGFjZSBjaGFyYWN0ZXIgKDEgJmxlOyBOICZsZTsgNSAmbWlkZG90OyAxMDxzdXA+NDxcL3N1cD4sIDEgJmxlOyBNICZsZTsgMTA8c3VwPjU8XC9zdXA+KS4gTiBpcyB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzLCBhbmQgTSBpcyB0aGUgbnVtYmVyIG9mIGVkZ2VzIG9mIGEgZ3JhcGguIFZlcnRpY2VzIGFyZSBpbmRleGVkIHdpdGggbnVtYmVycyAxIHRocm91Z2ggTi4gRWFjaCBvZiB0aGUgbmV4dCBNIGxpbmVzIGNvbnRhaW4gdGhyZWUgaW50ZWdlcnMgYSwgYiwgdywgc2VwYXJhdGVkIGJ5IGEgc3BhY2UgY2hhcmFjdGVyICgxICZsZTsgYSwgYiAmbGU7IE4sIDEgJmxlOyB3ICZsZTsgMjxzdXA+MzA8XC9zdXA+KSwgbWVhbmluZyB0aGF0IHRoZXJlIGlzIGFuIGVkZ2Ugb2Ygd2VpZ2h0IHcgYmV0d2VlbiB2ZXJ0aWNlcyBhIGFuZCBiLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPldyaXRlIG9uZSBpbnRlZ2VyIEsgZm9sbG93ZWQgYnkgYSBuZXdsaW5lLCB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIG1pbmltdW0gc3Bhbm5pbmcgdHJlZXMgbW9kdWxvIDEwMDAwMDMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d