树上小游戏

缪神是全村人的希望，因此大人们都会对孩子们说“你们一定要向你们的缪神哥哥学习！”。于是，村里的海尔兄弟寒假最喜欢做的事就成了抢着给缪神捶背。但是快被他们捶出颈椎病的缪神觉得这样下去不是办法，于是给他们出了一个小游戏，只有赢的人才能获得给自己捶背的资格。
缪神随手就能画出一棵带边权树（即一张n个点、n-1条边的连通图，其中每条边都有一个权值）。海尔兄弟在看不到边的情况下各从n个点中选一个点（一共 n * n 种可能的情况），如果两个点之间的唯一路径权值和是3的倍数，则海尔哥哥赢，否则海尔弟弟赢。
海尔哥哥和缪神一样富有好奇心，游戏结束后总会进行复盘，希望能计算出每次自己获胜的概率。于是他找到你，请你帮助他计算。

第一行一个整数n（1≤n≤1e5），表示树上的点个数。
接下来n-1行，第i行用三个整数ui vi wi表示第i条边，即ui与vi点之间有一条权值为wi的双向边。（1≤ui≤n， 1≤vi≤n， 0≤wi≤1e6）

输出两个用空格隔开的整数ai bi，即海尔哥哥获胜的概率为 ai/bi。

ai 与bi 需要互质，若概率为1则输出"1 1"。

5
1 2 1
1 3 2
1 4 1
2 5 3

13 25

样例说明 答案中的13组为：(1,1) (2,2) (2,3) (2,5) (3,2) (3,3) (3,4) (3,5) (4,3) (4,4) (5,2) (5,3) (5,5)。