/* ` ` ` ` ` ` ` ` `!!!;' ` '%$@########################&&%:. ` .%###################################%. ` .`|######################################% ` .!@###############################################$' ` .!@#########################@@@#########################&;. ` :@##################@@@&&@@@$!!%&@@@@@@@###################&' ` :&################@@@&$%%||||!!:'':;!!||%|!%&@@#################%` ` |###############@@&&$%|!;;::::':'''':::;;!!|%%%$&&@###############$` ` :&#############@&$%||||!;'````````````'''```'':::'':!|$@@###############; ` :@#############@$$%|!;;;;:'``````...```...`...`'':::''';|%$$$&############&' ` |##############&$$$%||!!;:'`````..````....`...```''::::;!!||$&&@@###########&' ` !##############@$%|!!!;::'''`````...``.....`````````'''::::;;::!|%$&############| ` :@##########@&%!:'`::;;:'``....```....... .``....````````````'':;!|%$@############; ` ;##########@%;```...`'''`... ..... ................ .`. `:!!!!%%%&#########| ` ;##########&|:.`'`. ..`... ....... ..... .. ..... ... .'':!!:.`''!@#########|. ` !##########|'`.;!` . ...... .. . .... .::'`. .. .`'|@########@: ` ;##########%'`'%! .. . . .. .```. ';:`..``.`':|@########@: ` !##########$:;$&; . `|%;. `;||;::`.``';;. .;!: `;:`';|$#########@!. ` !##########@$&@|. ...... .`':!|;` !$|%%'!##$' `|####$:`:;:!&$:. '$&!';!!||%&############; ` `$#############&: `!!'`:;;;||%@&!'!&&$;.|##%`.|#####%`'$@$&##%` .:||;;;;%@##############! ` :@#############|. .!&@|;%@@@@@&@@#@&@#@&@############@@#####@: .`'%@%!!&###############! ` :@############@; :&@!;$###@|%|!$@@######################@%` .;|!;!|%@###############! ` :@############@: `$#$%#@@##&@################@$$$&$%|!' `%#@|;':|&###############! ` !##########@$%: |####@&######$;. ..`'` ;@##############! ` !##########! ;#########|. `;` ;###############! ` ;##########; `%######; '$###&: `%@############&' ` !########@: .'. .:;` .|%: !##########&' ` !########@: ;#########@: ` !######%. !##&;. . `%&!` '&###&' !#########! ` |#######;.%###! `!&###@|;;%@###%. ';;|&$:;;` |#%. .%###%$###! ` !#######| `%#&' |##&$####&: !##########; `%#####%.!#|. .%@: ;###;`%##! ` !#$!$##! :@#! .|###$'. ;##|. :&#@; .``::` ;@|. :@#@: `$#| ` :&&|&##; :&#! :&##; .%##! !&' ;@##! |#! ` |@@##@; .`%#! '$##; ;##$` :@! .|##@; :&! ` !&|&##%:'. :&! :@#%. .%##; |&!. `|@! `$! ` '$%%###&;. '&&' `%##&' |##@&: ...;&&&@; .;&#|':;$&: ` .|######&; '$@@@@@@@@#| :&######%` ` !#####&: '$#####@: ` '$#####@: ;#####$` ` '&####%. `` '$#####; ` !#####$' |@: .:%|;;;;!$#####@#| '&###$: ` :&####&: ;####################@: ':` `%###@: ` ;#####@%:. `'';|@######$` ` `$######@|` !#&||@#####$` ` :&######@%'. .`''''` .';!|%@#@$$@####&: ` |######@|'. ;##$!!%@##########################@: '$####; ` :&#####$;''.`%#########&' `|@$: .%###@; ` :@####@; |#@##&$; `|%' .|####! ` !####@; . |####! ` :@###@|` . `|!. |####%. ` .|####! `;$@%|!!!!!%&&@#$;. !#####| ` .%####&: '%&@@@|` '&#####| ` .%#####|. :&######%` ` :|||;` !#######; .%#####@@#####@$;. ` `$#############&%!%#####|. :@####%:..'!&######@; ` `$#############|`..'%#######! ;####&;. .'%#######! ` .|##############@!` .'%#########%'. '%#####%` :@#######@%;:. ` ;%|;. !############%::;' `!&############@&&@#######@%' !###########&' ` !################$' .:' '|&######################$:. :@#############@@@@@@; ` ';$##&;:&###########$` :|$@################%:. !#####################@; ` '%####@$!:. `%#########! .:!%&@#######@%!;'. |##############%!$@####! ` .|#######&;'. . |#######%. .':;!!!!!!;`... .|############|. :$@@####%. ` !####&$&@#@!:'. ;#####%` .`';;'... ..''``. !##########%` ''':$######$` ` ;#####@$$;`%&:. `%####; .:;;:'':;||!:` !#########! :&#@@####! ` '%######@######! !! :$@$` ...`.'::`.. '$######@!` '|$$&!!@#######@!. ` '$#########@&$$@######@: ;: . `' .... ...``. `$######&' '!;`'!@######&&########$' ` ;############@#@@@@@$|%@###$` `!!.;' . :!. .%#####!. .;::&####|`..` ..;@########!' |########&|;'``..`:' ..!##%:. ;; `. .|###|` `'|###@&$|` .. .`|&&@#######%: |###@#@@#&|:`.`';;:;!!!;:;''!$##&;'. .'%; .;&###&|$! '$; .|$:;|` ...;&###$' .... :||%&########%: |#######@$;!%%:``` .!@###&|` :|'!########@#! ;@! :@####%'. `|@###&: ..`:::%$$&$$$&@##@@@##|: |########$;::'` .`. `%#####%!: .. !#####%` !#%. !; '%; !#############&: `::`.```. .':. :$@&&&###|: !####@%:::;;:::::` ......... '. !#######%;;';; `%#&' ;&: `;``$@!%########&&##&|::::'. ':. `!%@@######|: !#####%;;::. ...... ....`.. .. '::!|&########$';%`.'` .;%: !#$';$%|&$!&##########$' `';;;;!&##&%||||||%;` .:|&###@###|: |#######|`... `|$&&$$!`.... ;$: :&#@: `'''``. .%########&' .%#@&$%$#####$` ....`:%&@@@@@@&&@@!`. .`'%@#######|' |######@@$: .`..`!@&$&&&&: ;@#######@@#$%@######&$; '%@##%!@###@&&@####%. `!&@@@@@$:..`..``.``... `|&####@@##!' ;###&|;::!&#&%%%%: .'::::;|$&&$%|'..;%%&#######%;$########@&#####%` '|@###; '%####$;::::::` '!|%%%%%%%%%&#$:'::.'%###|' `%###@|;|%$%$@#&|;::::` '|%%%%%$%|%|;';$##@|'. |######&' .:|$%: :&@|'. !####%. `::;:!$@######&%%%%%!' ':;&##|: '$##%:. :&##@####@$;. .. `$| :; !#####| '|%: `` ... !####! . ..:&#@@@@##@&||$; :&####|' !####&@@&; ...`.'%@##@@#@@&!` :&&!. !###&' :||:.` !%' ``:$######@@@&&@@@&@##$;``.... |@@@@########!' !#######@$||!: ';!;;;!&###&|||||||||||%&##@!`. !###&||%!!!: .:;` `;;%####$;:;;;;;;;;;;;::. '||||||&#####%!;;$##!` `%#&:.`:!||||||%@#@%;::;;;' ;@@: .. .%###|. `:::' .:!;'`':'` `$####! ':;;;;!%@@&%%%|;` `;%&###|: .%##|.. '$##@@@@@@#&:...`.. `$#$' !##%` ..`.`:%@@! '%@$:''. .`|####|... .........`:%###@#@@@|` ....`%#####|: !###@&! .`.```':!&##@&&&&$: '&#%. !#&' ````. .```:%&&&&&@#####@!':|$&&$&&&&&&&&&@##|`````. !@@@#######!' :&#########@$||||: `::::;;;;;!!;;;:;$###$' .'` |#@|. .:;;:. `%####%:''':::::` `!||&##$;;;:::. ;##|: .%#@$%$%%%%%$@###$::::::'. ...`;|!::!&##@$%|||!' .%##&%%$%' `'. :&####! .':::'::%@&$%%!` .!!':;$###%: :&#############@|. . '$##################&;..!@###@#######%'. .!#####! . `$#####@|``;&|!&####|: |####&%' .''''':|@###@$$$$$$%;. |####%` .|#@;. .;$$$%$&$$$$$$&######$:..:|%$$$$$$$&&&&@######&;'''. ;$&########|: |#######@%;;` '!|!||$#######&|!!!;;;!!!;`.!#####@: .;|!!|&#$' `:'':;;$######################################%!|!!!!!;. .`;|&######@####%: |############$!''''..';$&&&&@########################$;'!;`:@#&:``'|$@######@@@@&&&&&&&@#######@&&&&&&&&&&&@@&&&&$|:. .`''$########@&@####%: |###&%$&#################@%;' .. `|@############$: `%@###########$` `%%:. . :@######| !#####################@$%&##########%: |#######################################@&&@######################@@&@#######################################################################%: */ #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; inline char gc() { static const int L = 233333; static char sxd[L], *sss = sxd, *ttt = sxd; if (sss == ttt) { ttt = (sss = sxd) + fread(sxd, 1, L, stdin); if (sss == ttt) { return EOF; } } return *sss++; } #ifndef _AT_HOME #define dd c = gc() #else #define dd c = getchar() #endif inline char readalpha() { char dd; for (; !isalpha(c); dd); return c; } inline char readchar() { char dd; for (; c == ' '; dd); return c; } template inline bool read(T& x) { bool flg = false; char dd; x = 0; for (; !isdigit(c); dd) { if (c == '-') { flg = true; } else if(c == EOF) { return false; } } for (; isdigit(c); dd) { x = (x * 10) + (c ^ 48); } if (flg) { x = -x; } return true; } #undef dd template inline void write(T x) { if (x < 0) { putchar('-'); x = -x; } if (x < 10) { putchar(x | 48); return; } write(x / 10); putchar((x % 10) | 48); } template inline void writesp(T x) { write(x); putchar(' '); } template inline void writeln(T x) { write(x); puts(""); } namespace dfcmd { const int maxn = 50005; const int maxm = 200005; const int inf = 0x3f3f3f3f; int n, m; struct Edge { int u, v, d; friend bool operator < (const Edge& a, const Edge& b) { return a.d < b.d; } } e[maxm]; struct LCT { int fa[maxn + maxm]; int s[maxn + maxm][2]; int lzy[maxn + maxm]; int mx[maxn + maxm]; int qz[maxn + maxm]; inline void push_up(int x) { mx[x] = max(qz[x], max(mx[s[x][0]], mx[s[x][1]])); } inline void rotate(int x) { int y = fa[x], d = s[y][1] == x; if (nrt(y)) { s[fa[y]][s[fa[y]][1] == y] = x; } fa[x] = fa[y]; s[y][d] = s[x][d ^ 1]; if (s[x][d ^ 1]) { fa[s[x][d ^ 1]] = y; } s[x][d ^ 1] = y; fa[y] = x; push_up(y); push_up(x); } inline bool nrt(int x) { return s[fa[x]][0] == x || s[fa[x]][1] == x; } inline void fan(int x) { lzy[x] ^= 1; swap(s[x][0], s[x][1]); } inline void push_down(int x) { if (lzy[x]) { if (s[x][0]) { fan(s[x][0]); } if (s[x][1]) { fan(s[x][1]); } lzy[x] = 0; } } inline void splay(int x) { static int sta[maxm + maxn]; int now = x, top = 0; sta[++top] = now; while (nrt(now)) { sta[++top] = now = fa[now]; } while (top) { push_down(sta[top--]); } while (nrt(x)) { int y = fa[x], z = fa[y]; if (nrt(y)) { rotate((s[y][0] == x) == (s[z][0] == y) ? y : x); } rotate(x); } } inline void access(int x) { for (int y = 0; x; x = fa[y = x]) { splay(x); s[x][1] = y; push_up(x); } } inline void make_root(int x) { access(x); splay(x); fan(x); } inline int find_root(int x) { access(x); splay(x); while (s[x][0]) { push_down(x); x = s[x][0]; } splay(x); return x; } inline void split(int x, int y) { make_root(x); access(y); splay(y); } inline void link(int x, int y) { // cout << "Link " << x << ' ' << y << endl; make_root(x); // cout << "fa[x] = " << x << ' ' << fa[x] << endl; fa[x] = y; } inline void cut(int x, int y) { // cout << "Cut " << x << ' ' << y << endl; split(x, y); splay(x); fa[y] = s[x][1] = 0; push_up(x); } inline void dfs(int now) { if (s[now][0]) { dfs(s[now][0]); } cout << now << ' '; if (s[now][1]) { dfs(s[now][1]); } } inline int link(int id) { int x = e[id].u, y = e[id].v; int mm = n + id; int ans = 0; // cout << "link " << x << ' ' << y << endl; if (find_root(x) == find_root(y)) { split(x, y); ans = mx[y]; int xx = e[ans].u, yy = e[ans].v; cut(n + ans, xx); cut(n + ans, yy); } link(mm, x); link(mm, y); /* cout << "dfs "; split(x, y); splay(y); dfs(y); cout << endl; */ return ans; } } tr; int Main() { // freopen("a.in", "r", stdin); read(n), read(m); for (int i = 1; i <= m; ++i) { read(e[i].u), read(e[i].v), read(e[i].d); tr.qz[i + n] = tr.mx[i + n] = i; } sort(e + 1, e + m + 1); set st; st.clear(); int ans = inf; for (int i = m; i; --i) { if (e[i].u == e[i].v) { continue; } int ct = tr.link(i); st.insert(i); // cout << i << ' ' << ct << endl; if (ct) { st.erase(ct); } if ((int) st.size() == n - 1) { ans = min(ans, e[*st.rbegin()].d - e[*st.begin()].d); } } writeln(ans); return 0; } } int main() { return dfcmd::Main(); } /* 5 7 1 3 1 1 2 2 2 3 3 3 4 4 2 4 5 2 5 6 4 5 7 */