#define pall pair<int,int>
using namespace std;
inline char get(){
static char buf[300],*p1=buf,*p2=buf;
return p1==p2 && (p2=(p1=buf)+fread(buf,1,30,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
register char c=get();register int f=1,_=0;
while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
return _*f;
}
struct edge{
int u,v,w,next;
}E[maxm];
struct cmp{
operator ()(const pall &a,const pall &b)const{
if(a.Y!=b.Y)return a.Y<b.Y;
return a.X<b.X;
}
};
int p[maxn],eid;
inline void init(){
for(register int i=0;i<maxn;i++)p[i]=-1;
eid=0;
}
inline void insert(int u,int v,int w){
E[eid].u=u;
E[eid].v=v;
E[eid].w=w;
E[eid].next=p[u];
p[u]=eid++;
}
inline void insert2(int u,int v,int w){
insert(u,v,w);
insert(v,u,w);
}
int n,m;
int dis[maxn],vis[maxn];
void dijkstra(int u){
pall note;
bool wait=1;
for(register int i=0;i<maxn;i++)dis[i]=0x3f3f3f3f,vis[i]=0;
dis[u]=0;vis[u]=1;
set<pall,cmp> s;
s.insert(make_pair(u,0));
for(register int i=0;i<n && s.size();i++){
set<pall,cmp>::iterator it=s.begin();
u=it->X;
s.erase(*it);
vis[u]=1;
for(register int j=p[u];~j;j=E[j].next){
int v=E[j].v;
int w=E[j].w;
if(dis[v]>dis[u]+w && !vis[v]){
s.erase(make_pair(v,dis[v]));
s.insert(make_pair(v,dis[v]=dis[u]+w));
note=make_pair(u,v);
}
}
if(wait){
dis[u]=0x3f3f3f3f;
vis[u]=0;
wait=0;
}
}
}
int u,v,w;
int main(){
freopen("1.txt","r",stdin);
init();
n=read();m=read();
for(register int i=0;i<m;i++){
u=read();v=read();w=read();
insert(u,v,1);
}
int ans=0x3f3f3f3f;
for(register int i=1;i<=n;i++){
dijkstra(i);
ans=min(ans,dis[i]);
}
cout<<ans<<endl;
return 0;
}
|