记录编号	578057	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	月考统计	最终得分	100
用户昵称	qwq	是否通过	通过
代码语言	C++	运行时间	0.299 s
提交时间	2023-01-29 11:39:53	内存使用	3.56 MiB

#include<bits/stdc++.h>

#define int long long
#define NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO int
#define _ (
#define $$$$$ )
#define ZHIYINNITAIMEI ; 
#define WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU [ 
#define YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO  ] 
#define QWERTYUIOPASDFGHJKLZXCBNMWOYUWENBUHAODANWOHUIXIEYUANSHENWOYINGYUBUHAODANWOHUIDUGENSHIN  for 
#define WoMenZheGeYaSuoMaoJinTiJiXiaoFangBianXieDai  if 
#define CHAIKAIYIBAOFANGSHUILIJIUBIANDAZENMECHEDOUCHEBUHUAI   else 
#define YONGLAICAJIAOCAZUIDOUSHIHENHAOYONGDE  { 
#define NIKANTADAKAIYIHOUXIANGYUANBINGYIYANGDAXIAO  } 
#define FANGZAISHUILIYUSHUIBIANDABIANGAO  void 

using namespace std ZHIYINNITAIMEI 

inline NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO read _  $$$$$  YONGLAICAJIAOCAZUIDOUSHIHENHAOYONGDE 
	NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO x=0,f=1 ZHIYINNITAIMEI char c=getchar _  $$$$$  ZHIYINNITAIMEI 
	 QWERTYUIOPASDFGHJKLZXCBNMWOYUWENBUHAODANWOHUIXIEYUANSHENWOYINGYUBUHAODANWOHUIDUGENSHIN  _  ZHIYINNITAIMEI  _ c<'0'||c>'9' $$$$$  ZHIYINNITAIMEI c=getchar _  $$$$$  $$$$$  YONGLAICAJIAOCAZUIDOUSHIHENHAOYONGDE  WoMenZheGeYaSuoMaoJinTiJiXiaoFangBianXieDai  _ c=='-' $$$$$ f=-1 ZHIYINNITAIMEI  NIKANTADAKAIYIHOUXIANGYUANBINGYIYANGDAXIAO 
	 QWERTYUIOPASDFGHJKLZXCBNMWOYUWENBUHAODANWOHUIXIEYUANSHENWOYINGYUBUHAODANWOHUIDUGENSHIN  _  ZHIYINNITAIMEI  _ c>='0'&&c<='9' $$$$$  ZHIYINNITAIMEI c=getchar _  $$$$$  $$$$$ x=x*10+ _ c&15 $$$$$  ZHIYINNITAIMEI 
	return x*f ZHIYINNITAIMEI 
 NIKANTADAKAIYIHOUXIANGYUANBINGYIYANGDAXIAO 

const NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO mod=1e9+7 ZHIYINNITAIMEI 
NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO ksm _ NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO x,NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO y,NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO p=mod $$$$$  YONGLAICAJIAOCAZUIDOUSHIHENHAOYONGDE 
	NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO ans=1 ZHIYINNITAIMEI 
	 QWERTYUIOPASDFGHJKLZXCBNMWOYUWENBUHAODANWOHUIXIEYUANSHENWOYINGYUBUHAODANWOHUIDUGENSHIN  _ NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO i=y ZHIYINNITAIMEI i ZHIYINNITAIMEI i>>=1,x=1ll*x*x%p $$$$$  WoMenZheGeYaSuoMaoJinTiJiXiaoFangBianXieDai  _ i&1 $$$$$ ans=1ll*ans*x%p ZHIYINNITAIMEI 
	return ans%p ZHIYINNITAIMEI 
 NIKANTADAKAIYIHOUXIANGYUANBINGYIYANGDAXIAO 
NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO inv _ NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO x,NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO p=mod $$$$$  YONGLAICAJIAOCAZUIDOUSHIHENHAOYONGDE return ksm _ x,p-2,p $$$$$ %p ZHIYINNITAIMEI  NIKANTADAKAIYIHOUXIANGYUANBINGYIYANGDAXIAO 
NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO randint _ NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO l,NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO r $$$$$  YONGLAICAJIAOCAZUIDOUSHIHENHAOYONGDE return rand _  $$$$$ *rand _  $$$$$ % _ r-l+1 $$$$$ +l ZHIYINNITAIMEI  NIKANTADAKAIYIHOUXIANGYUANBINGYIYANGDAXIAO 
 FANGZAISHUILIYUSHUIBIANDABIANGAO  add _ NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO &x,NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO v $$$$$  YONGLAICAJIAOCAZUIDOUSHIHENHAOYONGDE x+=v ZHIYINNITAIMEI  WoMenZheGeYaSuoMaoJinTiJiXiaoFangBianXieDai  _ x>=mod $$$$$ x-=mod ZHIYINNITAIMEI  NIKANTADAKAIYIHOUXIANGYUANBINGYIYANGDAXIAO 

const NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO NISHUODEDUIDANSHIYUANSHENSHIYIKUANYOUMIHAYOUZIZHUYANFADEKAIFANGSHIJIEMAOXIANYOUXIHOUMIANWANGLE=1005 ZHIYINNITAIMEI 
const NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO M=10005 ZHIYINNITAIMEI 
struct Edge YONGLAICAJIAOCAZUIDOUSHIHENHAOYONGDE 
	NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO to,cost ZHIYINNITAIMEI 
	Edge _ NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO T,NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO C $$$$$ :to _ T $$$$$ ,cost _ C $$$$$  YONGLAICAJIAOCAZUIDOUSHIHENHAOYONGDE  NIKANTADAKAIYIHOUXIANGYUANBINGYIYANGDAXIAO 
	Edge _  $$$$$  YONGLAICAJIAOCAZUIDOUSHIHENHAOYONGDE  NIKANTADAKAIYIHOUXIANGYUANBINGYIYANGDAXIAO 
 NIKANTADAKAIYIHOUXIANGYUANBINGYIYANGDAXIAO  ZHIYINNITAIMEI 
vector<Edge>G WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU NISHUODEDUIDANSHIYUANSHENSHIYIKUANYOUMIHAYOUZIZHUYANFADEKAIFANGSHIJIEMAOXIANYOUXIHOUMIANWANGLE YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO  ZHIYINNITAIMEI 
queue<NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO>q ZHIYINNITAIMEI 
NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO dis WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU NISHUODEDUIDANSHIYUANSHENSHIYIKUANYOUMIHAYOUZIZHUYANFADEKAIFANGSHIJIEMAOXIANYOUXIHOUMIANWANGLE YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO ,n,m,cnt WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU NISHUODEDUIDANSHIYUANSHENSHIYIKUANYOUMIHAYOUZIZHUYANFADEKAIFANGSHIJIEMAOXIANYOUXIHOUMIANWANGLE YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO  ZHIYINNITAIMEI 
bool inq WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU NISHUODEDUIDANSHIYUANSHENSHIYIKUANYOUMIHAYOUZIZHUYANFADEKAIFANGSHIJIEMAOXIANYOUXIHOUMIANWANGLE YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO  ZHIYINNITAIMEI 

 FANGZAISHUILIYUSHUIBIANDABIANGAO  spfa _ NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO s $$$$$  YONGLAICAJIAOCAZUIDOUSHIHENHAOYONGDE 
	memset _ dis,63,sizeof _ dis $$$$$  $$$$$  ZHIYINNITAIMEI 
	memset _ cnt,0,sizeof _ cnt $$$$$  $$$$$  ZHIYINNITAIMEI 
	q.push _ s $$$$$ ,dis WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU s YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO =0,inq WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU s YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO =1 ZHIYINNITAIMEI 
	while _ q.size _  $$$$$  $$$$$  YONGLAICAJIAOCAZUIDOUSHIHENHAOYONGDE 
		NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO u=q.front _  $$$$$  ZHIYINNITAIMEI q.pop _  $$$$$  ZHIYINNITAIMEI 
		 QWERTYUIOPASDFGHJKLZXCBNMWOYUWENBUHAODANWOHUIXIEYUANSHENWOYINGYUBUHAODANWOHUIDUGENSHIN  _ auto e:G WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU u YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO  $$$$$  YONGLAICAJIAOCAZUIDOUSHIHENHAOYONGDE 
			NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO v=e.to,w=e.cost ZHIYINNITAIMEI 
			 WoMenZheGeYaSuoMaoJinTiJiXiaoFangBianXieDai  _ dis WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU v YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO <=dis WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU u YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO +w $$$$$ continue ZHIYINNITAIMEI 
			dis WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU v YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO =dis WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU u YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO +w,cnt WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU v YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO =cnt WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU u YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO +1 ZHIYINNITAIMEI 
			 WoMenZheGeYaSuoMaoJinTiJiXiaoFangBianXieDai  _ cnt WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU v YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO >n $$$$$  YONGLAICAJIAOCAZUIDOUSHIHENHAOYONGDE puts _ "SOMEONE LAY!" $$$$$  ZHIYINNITAIMEI exit _ 0 $$$$$  ZHIYINNITAIMEI  NIKANTADAKAIYIHOUXIANGYUANBINGYIYANGDAXIAO 
			 WoMenZheGeYaSuoMaoJinTiJiXiaoFangBianXieDai  _ !inq WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU v YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO  $$$$$ q.push _ v $$$$$  ZHIYINNITAIMEI 
		 NIKANTADAKAIYIHOUXIANGYUANBINGYIYANGDAXIAO 
	 NIKANTADAKAIYIHOUXIANGYUANBINGYIYANGDAXIAO 
 NIKANTADAKAIYIHOUXIANGYUANBINGYIYANGDAXIAO 

NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO fr WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU M YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO ,to WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU M YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO ,val WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU M YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO ,Ans WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU NISHUODEDUIDANSHIYUANSHENSHIYIKUANYOUMIHAYOUZIZHUYANFADEKAIFANGSHIJIEMAOXIANYOUXIHOUMIANWANGLE YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO  ZHIYINNITAIMEI 

signed main _  FANGZAISHUILIYUSHUIBIANDABIANGAO  $$$$$  YONGLAICAJIAOCAZUIDOUSHIHENHAOYONGDE 
	
	freopen _ "ExamStat.in","r",stdin $$$$$  ZHIYINNITAIMEI 
	freopen _ "ExamStat.out","w",stdout $$$$$  ZHIYINNITAIMEI 
	
	n=read _  $$$$$ ,m=read _  $$$$$  ZHIYINNITAIMEI 
	 QWERTYUIOPASDFGHJKLZXCBNMWOYUWENBUHAODANWOHUIXIEYUANSHENWOYINGYUBUHAODANWOHUIDUGENSHIN  _ NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO i=1 ZHIYINNITAIMEI i<=m ZHIYINNITAIMEI i++ $$$$$  YONGLAICAJIAOCAZUIDOUSHIHENHAOYONGDE NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO u=read _  $$$$$ ,v=read _  $$$$$ ,w=read _  $$$$$  ZHIYINNITAIMEI G WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU u YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO .push_back _ Edge _ v,w $$$$$  $$$$$  ZHIYINNITAIMEI  NIKANTADAKAIYIHOUXIANGYUANBINGYIYANGDAXIAO 
	
	NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO s=0,t=n+1 ZHIYINNITAIMEI 
	 QWERTYUIOPASDFGHJKLZXCBNMWOYUWENBUHAODANWOHUIXIEYUANSHENWOYINGYUBUHAODANWOHUIDUGENSHIN  _ NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO w=0 ZHIYINNITAIMEI w<10 ZHIYINNITAIMEI w++ $$$$$  YONGLAICAJIAOCAZUIDOUSHIHENHAOYONGDE 
		G WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU s YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO .clear _  $$$$$ ,G WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU t YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO .clear _  $$$$$  ZHIYINNITAIMEI 
		 QWERTYUIOPASDFGHJKLZXCBNMWOYUWENBUHAODANWOHUIXIEYUANSHENWOYINGYUBUHAODANWOHUIDUGENSHIN  _ NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO i=1 ZHIYINNITAIMEI i<=n ZHIYINNITAIMEI i++ $$$$$  YONGLAICAJIAOCAZUIDOUSHIHENHAOYONGDE 
			 WoMenZheGeYaSuoMaoJinTiJiXiaoFangBianXieDai  _  _ i>>w $$$$$ &1 $$$$$ G WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU s YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO .push_back _ Edge _ i,0 $$$$$  $$$$$  ZHIYINNITAIMEI 
			 CHAIKAIYIBAOFANGSHUILIJIUBIANDAZENMECHEDOUCHEBUHUAI  G WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU t YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO .push_back _ Edge _ i,0 $$$$$  $$$$$  ZHIYINNITAIMEI 
		 NIKANTADAKAIYIHOUXIANGYUANBINGYIYANGDAXIAO 
		spfa _ s $$$$$  ZHIYINNITAIMEI  QWERTYUIOPASDFGHJKLZXCBNMWOYUWENBUHAODANWOHUIXIEYUANSHENWOYINGYUBUHAODANWOHUIDUGENSHIN  _ NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO i=1 ZHIYINNITAIMEI i<=n ZHIYINNITAIMEI i++ $$$$$  WoMenZheGeYaSuoMaoJinTiJiXiaoFangBianXieDai  _ ! _  _ i>>w $$$$$ &1 $$$$$  $$$$$ Ans WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU i YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO =min _ Ans WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU i YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO ,dis WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU i YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO  $$$$$  ZHIYINNITAIMEI 
		spfa _ t $$$$$  ZHIYINNITAIMEI  QWERTYUIOPASDFGHJKLZXCBNMWOYUWENBUHAODANWOHUIXIEYUANSHENWOYINGYUBUHAODANWOHUIDUGENSHIN  _ NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO i=1 ZHIYINNITAIMEI i<=n ZHIYINNITAIMEI i++ $$$$$  WoMenZheGeYaSuoMaoJinTiJiXiaoFangBianXieDai  _  _ i>>w $$$$$ &1 $$$$$ Ans WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU i YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO =min _ Ans WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU i YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO ,dis WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU i YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO  $$$$$  ZHIYINNITAIMEI 
	 NIKANTADAKAIYIHOUXIANGYUANBINGYIYANGDAXIAO 
	 QWERTYUIOPASDFGHJKLZXCBNMWOYUWENBUHAODANWOHUIXIEYUANSHENWOYINGYUBUHAODANWOHUIDUGENSHIN  _ NISHUODEDUIDANSHIWOMEITIANWANYUANSHENKEYIDEDAOYIBAIWUSHIYUANSHIMEIGEYUEJIUSHIDAGAIWUQIANYUANSHIZHEXIANGDANGYUSANWANMEIYUANZHEYIJINGCHAOGUOLEDABUFENZHONGGUORENDESHOURUSHUIPINGBAOKUONIZHEJIUSHIYUANSHENGEIWODEJIAOAO i=1 ZHIYINNITAIMEI i<=n ZHIYINNITAIMEI i++ $$$$$ cout<<-Ans WUZHISHIDIHUIYUANSHENDONGSHISHILIJIEYUANSHENCHENGSHUSHIYAOCHENGWEIYUANYOU i YUANSHENZUILIANGDEYUESHILIYUEYUANSHENZUIMEIDEYUJIAOGANYUYUANSHENZUITIANDETAOJIAOHUTAO <<" " ZHIYINNITAIMEI puts _ "" $$$$$  ZHIYINNITAIMEI 

	return 0 ZHIYINNITAIMEI 
 NIKANTADAKAIYIHOUXIANGYUANBINGYIYANGDAXIAO