{"trustable":true,"sections":[{"title":"Background","value":{"format":"MD","content":"这是一道经典题。"}},{"title":"Description","value":{"format":"MD","content":"给定 $n$ 个点 $m$ 条边的无向连通图,边有边权。 \n\n设一个自然数集合 $S$ 的 $\\text{mex}$ 为:最小的、没有出现在 $S$ 中的自然数。 \n\n现在你要求出一个这个图的生成树,使得其边权集合的 $\\text{mex}$ 尽可能小。"}},{"title":"Input","value":{"format":"MD","content":"第一行输入两个正整数 $n,m$。\n\n接下来 $m$ 行,每行 $3$ 个非负整数 $u,v,w$,表示 $u,v$ 之间有一条权值为 $w$ 的边。\n"}},{"title":"Output","value":{"format":"MD","content":"输出一行一个自然数,表示最小的 $\\text{mex}$ 值。"}},{"title":"Sample 1","value":{"format":"HTML","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 3\n1 2 0\n2 3 1\n3 2 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"MD","content":"【数据范围】 \n- 对于 $20\\%$ 的数据,$1\\le n \\le 100$,$1\\le m \\le 200$。\n- 对于 $50\\%$ 的数据,$1\\le n \\le 2000$,$1\\le m \\le 3000$。\n- 对于 $80\\%$ 的数据,$1\\le n \\le 10^5$,$1\\le m \\le 2\\times 10^5$。\n- 对于 $100\\%$ 的数据,$1\\le n \\le 10^6$,$1\\le m \\le 2\\times 10^6,0\\le w \\le 10^5$。\n\n输入数据规模较大,建议使用高效的读入方式。"}}]}