还不会双连通分量的朋友，请扣->这里<-
题意：
No response.
思路：
注意连通么？重边怎么处理啊？answer=0，听说还需要人。
The solution. 1th.处理连通的话，推荐BFS！如果涉及图遍历问题！BFS！你以为DFS标记掉复杂度就低了么？ 2nd.重边处理的话，从u->v避免v->u. 在利用链式前向星存储图，利用异或，like: 0^1=1,1^1=1,2^1=3,3^1=2…
n(n%2==0)
^
1=n+1
,
(n+1)
^
1=n
. 每次对于编号为 i 的边，如果
i
^ 1=pre，pre即为父节点的那条边 ，则不处理这条边。那如果判断前驱结点 == v是错的。为啥呢？ 因为那样处理是单单处理了 “一条无向边”，两个结点的“多条边”的地位是等价的，如果记录前驱结点，判断掉，只会处理两个结点的“多条边”其中的“一条边”。在这里，要求边的最小权值，然后如果用记录前驱结点，判断掉，这样DFS只遍历到了两个结点间的一条边。 3rd.咳咳.
这样写题解好累啊……算了，自娱自乐吧。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<math.h>
#include<algorithm>
typedef long long LL;
using namespace std;
const int INF=
0x3f3f3f3f;
const int N=
1e3+
10;
struct Edge{
int w;
int to;
int next;
bool cut;
}edge[N*N];
int tol,head[N],n,m;
void init(){
tol=
0;
memset(head,-
1,
sizeof(head));
}
void add(
int u,
int v,
int w){
edge[tol].w=w;
edge[tol].to=v;
edge[tol].next=head[u];
head[u]=tol++;
}
bool vis[N],flag[N];
int low[N],dfn[N];
int ind;
int Max;
void Tarjan(
int u,
int pre)
{
int v;
low[u]=dfn[u]=ind++;
vis[u] =
true;
for(
int i=head[u]; ~i; i=edge[i].next){
v=edge[i].to;
if((i^
1)==pre)
continue;
if(!dfn[v]){
Tarjan(v,i);
low[u]=min(low[u],low[v]);
if(dfn[u] < low[v])
Max=edge[i].w<Max?edge[i].w:Max;
}
else
low[u]=min(low[u],dfn[v]);
}
}
void solve(){
memset(flag,
false,
sizeof(flag));
memset(dfn,
0,
sizeof(dfn));
memset(low,
0,
sizeof(low));
memset(vis,
false,
sizeof(vis));
ind=
1;
Max = INF;
Tarjan(
1,-
1);
if(Max == INF)
puts(
"-1");
else
{
if(!Max) Max=
1;
printf(
"%d\n",Max);
}
}
int num;
queue<int>que;
int BFS(){
memset(vis,
false,
sizeof(vis));
while(!que.empty()) que.pop();
int res=
0,u,v;
que.push(
1);
vis[
1]=
true;
while(!que.empty()){
u = que.front();que.pop();
res++;
for(
int i=head[u];~i;i=edge[i].next)
{
v=edge[i].to;
if(vis[v])
continue;
vis[v]=
true;
que.push(v);
}
}
return res;
}
int main(){
int u,v,w;
while(
scanf(
"%d%d",&n,&m)){
if(!n && !m)
break;
init();
while(m--){
scanf(
"%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
if(BFS()<n){
puts(
"0");
continue;
}
solve();
}
return 0;
}
