{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"### Read problem statements in [Hindi](https://www.codechef.com/download/translated/JULY19/hindi/MXMN.pdf), [Bengali](https://www.codechef.com/download/translated/JULY19/bengali/MXMN.pdf), [Mandarin Chinese](https://www.codechef.com/download/translated/JULY19/mandarin/MXMN.pdf), [Russian](https://www.codechef.com/download/translated/JULY19/russian/MXMN.pdf) and [Vietnamese](https://www.codechef.com/download/translated/JULY19/vietnamese/MXMN.pdf) as well.\r\n\r\nChef loves graphs. To express his love, he defines a function $f(G, x, y)$ for an undirected connected graph $G$ with weighted edges and two of its vertices $x$, $y$. $f(G, x, y)$ is defined as the minimum of weights of all paths in $G$ between the vertices $x$ and $y$, where the weight of a path is the maximum of weights of edges in this path.\r\n\r\nChef has two connected graphs $G_1$ and $G_2$. Each of these graphs has $N$ vertices (labelled $1$ through $N$) and $M$ edges. Calculate $$S \u003d \\sum_{i\u003d1}^{N-1} \\sum_{j\u003di+1}^N f(G_1, i, j) \\cdot f(G_2, i, j)$$ modulo $998,244,353$.\r\n\r\n### Input\r\n- The first line of the input contains two space-separated integers $N$ and $M$.\r\n- $M$ lines follow. Each of these lines contains three space-separated integers $u$, $v$ and $w$ denoting that vertices $u$ and $v$ in $G_1$ are connected by an edge with weight $w$.\r\n- $M$ more lines follow. Each of these lines contains three space-separated integers $u$, $v$ and $w$ denoting that vertices $u$ and $v$ in $G_2$ are connected by an edge with weight $w$.\r\n\r\n### Output\r\nPrint a single line containing one integer — the sum $S$ modulo $998,244,353$.\r\n\r\n### Constraints\r\n- $1 \\le N \\le 10^5$\r\n- $M \u003d 2N$\r\n- $1 \\le u, v \\le N$\r\n- $1 \\le w \\le 10^8$\r\n- $G_1$ and $G_2$ are connected graphs\r\n\r\n### Subtasks\r\n**Subtask #1 (20 points):** $N \u003d 2,000$\r\n\r\n**Subtask #2 (30 points):**\r\n- $N \u003d 10^5$\r\n- $G_1$ and $G_2$ are identical graphs\r\n\r\n**Subtask #3 (50 points):** original constraints"}},{"title":"Sample 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 6\r\n1 2 3\r\n2 3 1\r\n3 1 2\r\n1 2 4\r\n2 3 5\r\n3 1 6\r\n1 2 2\r\n2 3 1\r\n3 1 3\r\n1 2 5\r\n2 3 4\r\n3 1 6\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e9\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}