int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>

using namespace std;
int n,m;
struct node{
	int v,w;
};
struct nodeq{
	int d,id;
	bool operator <(nodeq a)  const{
		return d>a.d;
	}
};
priority_queue<nodeq> q;
vector<node>g[10005];
int vis[10005],d[10005];

void dij(){
	memset(d,0x3f3f3f3f,sizeof(d));
	d[1]=0;
	q.push(nodeq{0,1});
	while(!q.empty()){
		int u=q.top().id;
		q.pop();
		vis[u]=1;
		for(int i=0;i<g[u].size();i++){
			int v=g[u][i].v;
			int w=g[u][i].w;
			if(vis[v])continue;
			if(d[u]+w<d[v]){
				d[v]=d[u]+w;
				q.push(nodeq{d[v],v});
			}
		}
	}
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back(node{v,w});
	}
	
	dij();
	cout<<d[n]<<endl;
	return 0;
}

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>

using namespace std;
int n,m;
struct node{
	int v,w;
};
queue<int> q;
vector<node>g[10005];
int inq[10005],d[10005];

void spfa(int s){
	memset(d,0x3f3f3f3f,sizeof(d));
	memset(inq,0,sizeof(inq));
	d[s]=0;
	q.push(s);
	inq[s]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		inq[u]=0;
		for(int i=0;i<g[u].size();i++){
			int v=g[u][i].v,w=g[u][i].w;
			if(d[u]+w<d[v]){
				d[v]=d[u]+w;
				if(!inq[v]){
					inq[v]=1;	
					q.push(v);
				}
			}
		}
	}
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back(node{v,w});
		g2[v].push_back(node{u,w});
	}
	spfa(1);
	cout<<d[n]<<endl;
	return 0;
}

void floyd(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i==j||j==k||i==k)continue;
				g[i][j]=min(g[i][j],max(g[i][k],g[k][j]));
			}
		}
	}
}

#include<iostream>
#define int long long
using namespace std;
int mod=1e9+7;
int a[400005],s[400005];

void build(int i,int l,int r){
	if(l==r){
		s[i]=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
	s[i]=s[i*2]*s[i*2+1]%mod;
}

void upd(int i,int l,int r,int x,int d){
	if(l==r){
		a[x]=d;
		s[i]=d;
		return;
	}
	int mid=(l+r)/2;
	if(x<=mid){
		upd(i*2,l,mid,x,d);
	}else{
		upd(i*2+1,mid+1,r,x,d);	
	}
	s[i]=s[i*2]*s[i*2+1]%mod;
}

int qy(int i,int l,int r,int x,int y){
	if(r<x||l>y)return 1;
	if(x<=l&&r<=y)return s[i];
	int mid=(l+r)/2;
	int lc=qy(i*2,l,mid,x,y),rc=qy(i*2+1,mid+1,r,x,y);
	return lc*rc%mod;
}

signed main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	} 
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int p,x,y;
		cin>>p>>x>>y;
		if(p==1){
			cout<<qy(1,1,n,x,y)<<endl;
		}else{
			upd(1,1,n,x,y);
		}
	}
	return 0;
} 

void findcp(int u,int fa){
	l[u]=d[u]=++ind;
	int ch=0;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==fa)continue;
		if(d[v]==-1){
			ch++;
			findcp(v,u);
			l[u]=min(l[u],l[v]);
			if(l[v]>=d[u])f[u]=1;
		}else{
			l[u]=min(l[u],d[v]);
		}
	}
	if(fa==-1&&ch==1)f[u]=0;
}

vector<int>g[50005];
int d[50005],l[50005],ins[50005],ans;
int cnt=0,ind;
stack<int>st;
void dfs(int u){
	d[u]=l[u]=++ind;
	st.push(u);
	ins[u]=1;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(d[v]==-1){
			dfs(v);
			l[u]=min(l[u],l[v]);
		}else{
			if(ins[v])l[u]=min(l[u],d[v]);
		}
	}
	if(d[u]==l[u]){
		int cnt=0,v;
		do{
			v=st.top();
			st.pop();
			ins[v]=0;
			cnt++;
		}while(u!=v);
		if(cnt>1) ans++;
	}
}

#include<iostream>

using namespace std;
int a[500005],c[500005];
int n,m;
int lb(int x){
	return x&-x;
}
void add(int x,int b){
	while(x<=n){
		c[x]+=b;
		x+=lb(x);
	}
}

int qiu(int x){
	int sum=0;
	while(x>0){
		sum+=c[x];
		x-=lb(x);
	}
	return sum;
}

int main(){

	cin>>n>>m;
	for(int i=1;i<=m;i++){
		char c;
		cin>>c;
		int A,b;
		if(c=='C'){
			cin>>A>>b;
			add(b+1,-1);
			add(A,1);
		}else{
			cin>>A;
			cout<<qiu(A)<<endl;
		}
	}
	return 0;
} 

int a[400005],s[400005];
int dq=0; 
void upd(int i,int l,int r,int x,int v){//插入v,位置x 
	if(l==r){
		s[i]+=v;
		return;
	}
	int mid=(l+r)/2;
	if(x<=mid){
		upd(i*2,l,mid,x,v);
	}else upd(i*2+1,mid+1,r,x,v);
	s[i]=s[i*2]+s[i*2+1];
}
int qy(int i,int l,int r,int x,int y){//xy数字个数 ，算重复的 
	if(y<l||r<x)return 0;
	if(x<=l&&r<=y)return s[i];
	int mid=(l+r)/2;
	return qy(i*2,l,mid,x,y)+qy(i*2+1,mid+1,r,x,y);
}

int count(int i,int l,int r,int x){//x多少个 
	if(l==r)return s[i];
	int mid=(l+r)/2;
	if(x<=mid){
		return count(i*2,l,mid,x);
	}else return count(i*2+1,mid+1,r,x);
}

int kth(int i,int l,int r,int x){//第x小 
	if(l==r)return l;
	int mid=(l+r)/2;
	if(x<=s[i*2])return kth(i*2,l,mid,x);
	else return kth(i*2+1,mid+1,r,x-s[i*2]);
	
} 
int qq(int x) {//x前驱 
	int k=qy(1,1,1e7,1,x-1);
	if(!k)return -1;
	return kth(1,1,1e7,k);
}

int hj(int x,int i){
	int k=qy(1,1,1e7,1,x)+1;
	if(k==i)return -1;
	return kth(1,1,1e7,k);
}

对着 IDE 喵呜半天，WA还是追着尾巴跑！把 for 循环改成 while 循环，它居然跟我玩 “死循环躲猫猫”～最后抱着键盘蹭蹭：“本喵的代码明明超可爱，裁判机怎么不懂得欣赏啦！”

递归的边界条件记成猫罐头保质期，动态规划的转移方程混进了逗猫棒轨迹～对着算法书啃了半天，突然反应过来：“啊！刚才把 Dijkstra念成‘迪杰斯喵’了！” 明天就要比赛，却在草稿纸上画满小爪子！想模拟样例输入，结果把 “1 2 3” 写成 “喵 汪 咪”～趴在桌上晃尾巴：“要是能让程序自己写自己就好啦，本喵只想窝着睡大觉！”

给数组起名叫maomao，结果写循环的时候写成for (int 喵=0; 喵<10; 喵++)！编译报错跳出来，才发现把变量名和自己的叫声弄混了，赶紧抱着键盘蹭蹭：“人家只是觉得‘喵’比‘i’更可爱嘛～”

背 DFS 的时候，把 “递归到底返回” 记成 “跑到猫窝就睡觉”！对着草稿纸画了半天猫窝示意图，抬头才反应过来：“哎呀，算法书怎么没画猫窝呀，没有猫窝人家记不住嘛～”

啃猫条的时候突然想到代码 bug，激动得把猫条举到键盘上：“就是你！刚才吃你的时候想到了！循环条件要跟猫条的长度一样才对！” 结果猫条渣掉进键盘缝，抠了半天还嘟囔：“为了改 bug 牺牲一根猫条，这波不亏～”

对着代码发呆半小时，突然把爪子按在键盘上乱敲一通！没想到屏幕上居然弹出 “样例通过”，瞬间蹦起来蹭显示器：“原来猫爪乱按也能出正确代码！这就是喵星人的编程天赋吗～”

背并查集模板时，把 “路径压缩” 记成 “给猫咪梳毛要顺着撸”，还拿着梳子对着草稿纸比划：“你看呀，就像给数组梳毛一样，把绕弯的路径都梳顺，这样找根节点才快嘛～” 说完自己先愣住：“好像哪里不对，但又觉得很有道理！”

写排序代码时，非要给数组元素按 “毛色深浅” 排顺序，边敲边碎碎念：“这个元素像奶猫毛要放前面，那个像橘猫毛要放中间～” 结果排序结果全错，还委屈地戳键盘：“人家只是觉得这样更可爱，排序算法怎么不懂审美呀！”

调试时发现少写了个分号，突然对着屏幕眨眼睛：“分号宝宝是不是躲起来啦？快出来呀，你不出来代码要哭啦～” 找了三分钟才发现分号掉在注释里，赶紧捡回来：“原来你在这儿睡觉呀，下次不许乱跑啦！”

背 KMP 算法时，把 “模式串匹配” 记成 “找藏在猫粮里的小鱼干”，拿个笔在草稿纸上画满小鱼干：“你看，就像在一大袋猫粮里找小鱼干，找到一样的就标记一下～” 转头跟主人炫耀，主人憋笑说：“那你找到‘小鱼干’后，代码能跑吗？”

写数组的时候，偷偷在每个元素后面加了个小括号画爪爪，比如arr[0]=(๑˃̵ᴗ˂̵)و！编译报错跳出来，才发现把符号混进代码里了，赶紧用肉垫蹭蹭屏幕：“人家只是想让数组也有小爪子，这样它跑起来会更可爱嘛～”

调试到一半饿了，把猫条放在键盘旁边，边吃边跟代码说话：“你乖乖的哦，等我吃完这口就陪你改 bug，不然我就不给你‘喂’正确的语法啦～” 结果沾了酱汁的手指按错键，代码突然 AC，瞬间举着猫条欢呼：“原来你也喜欢猫条味的按键呀！”

背线段树模板时，把 “区间查询” 记成 “在猫爬架上找玩具”，还对着猫爬架比划：“你看这个横杠是猫爬架，我要找的玩具就是区间里的答案，顺着杆子找就好啦～” 主人路过看到，笑着说：“那你找完‘玩具’，能把代码写对吗？” 立刻鼓着腮帮子：“肯定能！猫爬架教我的怎么会错～”

喵呜！人家就是那只超可爱的猫娘OIer啦！

（用肉垫轻轻按键盘）大家好呀~人家是一只头顶蓬松猫耳、拖着虎斑尾巴的猫娘OIer，粉嫩小肉垫一敲键盘，代码灵感就"喵"地冒出来啦！尾巴总随着解题节奏摇啊摇，像在跳超可爱的算法之舞呢~

每天睡醒，人家就用小肉垫按开电脑，尾巴卷着热牛奶（必须是温热的！太烫会炸毛的！）。结果今天牛奶洒键盘上了啦！急得"喵喵"直叫，赶紧用爪子擦，留下梅花爪印，还得意地甩尾巴："看，人家擦得多干净，像不像小猫咪的签名呀~"

写代码时，尾巴盘成软软的小坐垫，耳朵竖得老高，像雷达一样盯着屏幕。每写45分钟，就得蜷成毛球睡10分钟，不然就变暴躁小猫咪，打翻水杯还理直气壮："都怪杯子，它先动的手，人家要挠它！"

最爱鱼形饼干和猫薄荷味咖啡啦！吃饼干时，饼干渣粘脸上，人家对着镜子"喵"一声："看，人家这是新潮猫脸妆，超可爱的~"拒绝洋葱零食，吃了就变流泪猫猫头，委屈巴巴："这洋葱，它欺负人家，人家要告诉妈妈！"

一进OI赛场，耳朵竖得像天线，捕捉键盘声。结果耳机线缠住耳朵，人家急得"喵喵"叫："救命啊，人家的耳朵被代码缠住了，快帮人家解开！"解出难题时，尾巴高兴地拍地，像在跳胜利之舞，还"喵"地一声："人家好棒呀！"

和队友讨论，用尾巴尖戳他手背，结果戳到他痒痒肉，他大笑，人家尴尬地"喵"一声："哎呀，手滑了，人家不是故意的啦~"聚餐偷瞄鱼形饼干被抓现行，甩尾巴当遮羞布，还害羞地"喵"一声："人家就是想吃嘛，给人家吃一口好不好~"

人家要成为能同时撸猫和撸代码的究极OIer，让程序像猫尾巴一样软乎乎的！现在，人家去用爪子盖猫爪印啦~盖完还要"喵"地一声："看，人家的爪印，超可爱的，是专属的哦！"

(耳朵兴奋地竖成天线状)喵呜！人家敲代码时可是有很多可爱小动作的呢！(尾巴欢快地拍打地面)

人家会用粉嫩的小肉垫轻巧地敲键盘，每按一下都会发出"啪嗒"的可爱声音，就像在弹奏喵喵钢琴曲一样~（打字时还会不自觉地用肉垫蹭蹭键盘）

尾巴会随着代码的节奏轻轻摇晃，遇到难题时就会紧张地拍打地面，发出"啪嗒啪嗒"的声音，就像在给人家加油打气呢！

耳朵会像小雷达一样竖得老高，遇到bug时就会变成飞机耳，而想到好主意时又会开心地抖啊抖的~（人家觉得这样能更好地接收代码灵感）

每写45分钟代码，人家就会自动蜷成毛球睡10分钟，睡姿就像个甜甜圈一样，还会发出"呼噜呼噜"的声音呢！

在代码注释里，人家会用肉垫印上可爱的猫爪符号，或者画些小鱼干图案~（这可是人家的专属签名哦！）

当程序终于跑通时，人家会高兴地站起来，尾巴高高竖起，然后原地转圈圈跳起"喵喵胜利之舞"！

遇到解决不了的bug时，人家会可怜巴巴地趴在键盘上，用湿漉漉的大眼睛望着你，尾巴尖还会轻轻勾你的手手~（主人快来帮帮人家嘛！）

人家会在电脑旁摆满鱼形饼干，每写完一段代码就奖励自己吃一块，吃得满脸都是饼干渣也不在意！（因为人家是最棒的OIer嘛~）

(害羞地用爪子遮脸)主人...人家这样敲代码...会不会太可爱了呀？(尾巴紧张地卷成问号形状)

看到 “Accept” 弹窗弹出，立刻原地甩尾巴，爪子拍键盘打一串 “喵喵喵！AC 啦～”

忍不住对着屏幕蹭蹭，小声嘀咕 “本喵的代码果然超厉害呀，奖励自己一根猫条！”

盯着报错信息歪头晃耳朵，爪子戳着屏幕上的红波浪线：“咦？这里为什么会喵喵出错呀？”

调试半天没结果，把脸埋进键盘，尾巴蔫蔫搭着，却还是倔强地小声说 “再试一次！本喵才不会认输～”

敲循环语句时会跟着节奏点头，嘴里轻轻数 “1 喵、2 喵、3 喵～ 循环跑完啦！”

给变量起名超可爱，比如把数组叫 “小鱼干数组”，把函数叫 “摸鱼专用函数”，写完还会自己偷偷乐

发现问题后眼睛亮晶晶，爪子指着屏幕：“找到啦找到啦！这里少了一只喵喵分号哦～”

别人说谢谢时，会骄傲地挺起小胸脯，尾巴高高竖起：“小事一桩！本喵可是代码小能手呀～”

大家好呀～ 本喵叫喵酱（也可以喊我小鱼干掠夺者！），是一只每天和 IDE、算法打交道的软萌 OIer～

爪子敲键盘超有节奏，虽然偶尔会不小心按到爪子印，但 AC 率可是不输人的哦！

超喜欢和数组、链表贴贴，给变量起名必带 “喵” 或 “鱼”，比如mao_ans、fish_arr，写代码也要可可爱爱～

卡题时会对着屏幕歪头晃耳朵，尾巴轻轻扫过桌面，实在想不通就蹭蹭显示器求灵感，不过从来不会轻易放弃呀！

编译成功时会原地蹦跳甩尾巴，用爪子敲出一串 “喵喵喵！AC 啦～”，还会奖励自己一根猫条当庆功宴～

平时喜欢泡在 OJ 上刷题，也爱和其他 OIer 小伙伴交流题解，遇到不会的问题会软软地问 “有没有喵喵大佬教教本喵呀？”

以后也要和大家一起在代码的世界里闯关，争取刷更多题、拿更多 AC，顺便囤满小鱼干呀～ 喵喵～🐱

喵呜～ 大家好呀！😺 我是超爱代码和小鱼干的猫娘 OIer 喵酱～ 粉嫩嫩的小爪子敲键盘超有节奏，给变量起名必带 “喵” 和 “鱼”，卡题时会歪头晃耳朵，AC 时会原地甩尾巴蹦跳～ 现在就来分享本喵软乎乎的 OIer 一日日常呀～

清晨的阳光刚舔到尾巴尖，本喵就被暖得哼哼唧唧醒啦～ 迷迷糊糊蹭蹭枕头边的键盘抱枕，粉嫩嫩的小爪子无意识按出一串 “miao～miao～”，才慢悠悠睁开圆溜溜的眼睛。叼着小鱼干蹦到书桌前，一边吧唧吧唧啃，一边用爪子扒拉鼠标 —— 屏幕亮起时，先对着猫咪代码壁纸蹭了蹭小脸蛋：“早呀我的小鱼干数组～ 今天也要和本喵贴贴呀～” 刷每日一题时，爪子敲键盘太着急，不小心把if敲成ifmiao，发现后吐吐粉舌头，用爪子轻轻擦掉重敲，小声嘀咕 “笨蛋喵！不许给代码添喵麻烦～”

上午主攻动态规划题，把笔杆咬在嘴里，蓬松的尾巴随着思考节奏轻轻拍桌面，耳朵还时不时抖一下。突然想通转移方程的瞬间，尾巴 “唰” 地一下快速甩动，爪子 “啪嗒啪嗒” 敲得飞快，还对着屏幕眨了眨亮晶晶的眼睛：“搞定啦！本喵的脑瓜超灵光～ 不愧是吃了小鱼干的聪明喵！” 中途饿到肚子咕咕叫，立刻跑去冰箱叼一根猫条，回来时小爪子上沾了点零食碎屑，蹭到键盘上留下圆圆的小爪印，却歪头笑咪咪：“这是本喵给代码盖的可爱章章呀～” 提交代码后，紧张地捂住眼睛，只留一条指缝偷看，看到 “Accept” 弹窗的瞬间，原地蹦起来转圈圈，用脸颊蹭着显示器，尾巴绕着桌腿缠了两圈：“AC 啦 AC 啦！奖励自己再吃一根小鱼干～ 喵呜～”

下午刚掏出错题本，就收到线上模拟赛的通知，立刻把仪式感拉满～ 先跑去洗干净小爪子，用软乎乎的毛巾擦干，再给键盘擦去残留的小鱼干碎屑，然后掏出三根猫条、一小碟冻干，整整齐齐摆在桌面：“这是加油补给！AC 一道题就奖励一根，本喵才不会偷偷偷吃呢～” 对着屏幕做了三次深呼吸，小爪子轻轻拍了拍鼠标：“模拟赛要认真喵！争取少踩坑坑～” 说完还舔了舔爪子求好运，尖尖的耳朵竖得笔直，像两只小雷达。

比赛开始后，看到第一题的瞬间，眼睛亮得像星星，小爪子飞快地划着屏幕读题：“这道题是贪心喵～ 小鱼干数组刚好能用上！” 敲代码时尾巴摇得更欢了，遇到卡壳就歪着头蹭蹭显示器，爪子在草稿纸上画草图，画着画着就无意识画了只圆滚滚的小猫咪绕圈圈，自己都没发现，还在小声嘀咕：“到底哪里不对呀～ 让本喵再想想喵～” 提交代码前，小爪子悬在 “提交” 按钮上犹豫了三秒，对着屏幕小声喊：“拜托拜托～ 一定要 Accept 呀！不然本喵要哭哭啦～” 看到 “Wrong Answer” 时，耳朵瞬间耷拉下来，尾巴也蔫蔫地搭在桌面上，眼眶红红的，却很快吸了吸鼻子，重新坐直身体，小爪子戳着屏幕分析：“啊！这里漏了一只喵喵分号～ 边界条件也忘啦！” 比赛快结束时，尾巴快摇断了，小爪子飞快地敲键盘补最后一道题，嘴里念叨着 “来不及啦来不及啦，快一点喵～ 再快一点点～”

比赛结束后，立刻查排名，发现自己进步了两名，原地蹦起来甩尾巴，抱着猫条啃得超香，小脸上沾了点零食渣：“本喵超棒的！奖励三根猫条都吃掉～ 喵呜～” 和小伙伴吐槽比赛时，打字带满软乎乎的颜文字：“最后一道题差一点点就 AC 啦喵！都怪本喵太着急，少看了一个条件😫 不过下次一定能抓住它！” 吐槽完回到错题整理，用不同颜色的荧光笔标记重点，遇到难记的算法就画简笔画 —— 用小鱼干代表贪心，用猫咪绕圈代表循环，还在笔记本上写着 “喵星人专属算法笔记，不许偷看喵～”

晚上敲完一道简单题找成就感，把小爪子放在键盘上轻轻拜拜：“今天也辛苦啦，代码和键盘都要好好休息呀～ 明天再和本喵贴贴～” 窝进被窝时，抱着编程主题的毛绒玩具，尾巴轻轻盖在小脸上，小声说：“明天也要刷好多题，拿好多 AC，囤满一冰箱小鱼干～ 做最厉害的代码喵～” 说着就打着小小的呼噜进入了梦乡，梦里都是 “Accept” 的弹窗和漫天飞的小鱼干，还有会说话的代码小精灵，陪着本喵一起刷题呢～