蒟蒻已经调了好几天啦QAQ

这几天我从99分的暴力，变成0分正解，又变成31，41，81，21，50……现在卡在81分再也上不去了，小数据也被我下载完过掉了

本蒟蒻不咋会图论，不喜请喷QAQ

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
int n,m,ans,no2,pr[1005],pre[1005],f[1005],fa[1005][15],id[1001],d[1005],cnt=0;
bool b[1005];
struct ed{
	int to;
	int val;
};
struct node{
	int point;
	int val;
	int nx;
    bool operator <(const node &x)const{
        return x.val<val;
    }
};
struct shu{
	int l,r,val;
}me[1000005];
priority_queue<node>q;
vector<ed>v[1005];
vector<int>tr[1005];
inline void dij(int ss){//最短路 
	memset(f,0x3f,sizeof(f));
	memset(b,false,sizeof(b));
	f[ss]=0;
	q.push((node){ss,0});
	while(q.size()){
		node u=q.top();q.pop();
		int p=u.point,s=v[u.point].size(),g;
		if(b[p])continue;
		b[p]=true;
		for(int i(0);i<s;++i){
			g=v[p][i].to;
			if(b[g])continue;
			if(f[g]>f[p]+v[p][i].val){
				f[g]=f[p]+v[p][i].val;
				pr[g]=p;
				q.push((node){g,f[g]});
			}
		}
	}
}
void dfs(int p,int bf,int de){//最短路树 
	fa[p][0]=bf;d[p]=de;
	for(int i(1);i<=14;++i)fa[p][i]=fa[fa[p][i-1]][i-1];
	for(int i(0);i<tr[p].size();++i)dfs(tr[p][i],p,de+1);
}
int lca(int x,int y){//倍增求lca 
	if(d[x]>d[y])swap(x,y);
	int h=d[y]-d[x],g=0;
	for(;h;h>>=1){
		if(h&1)y=fa[y][g];
		++g;
	}
	if(x==y)return x;
	for(int i(14);~i;--i){
		if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	}
	return fa[x][0];
}
bool cmp(shu x,shu y){
	return x.val>y.val;
}
struct tree{
	int ll,rr,val,tag;
}t[100005];
void build(int l,int r,int p){//建线段树 
	t[p].ll=l,t[p].rr=r,t[p].val=0x7fffffff,t[p].tag=0x7fffffff;
	if(l==r)return;
	int mid=l+r>>1;
	build(l,mid,2*p),build(mid+1,r,2*p+1);
}
void up(int p){//上传 
	t[p].val=max(t[2*p].val,t[2*p+1].val);
}
void spread(int p){//下传 
	if(t[p].tag!=0x7fffffff){
		t[2*p].tag=min(t[2*p].tag,t[p].tag);
		t[2*p+1].tag=min(t[2*p+1].tag,t[p].tag);
		t[2*p].val=min(t[2*p].val,t[p].tag);
		t[2*p+1].val=min(t[2*p+1].val,t[p].tag);
		t[p].tag=0x7fffffff;
	}
}
void assign(int l,int r,int z,int p){//区间赋值 
	if(t[p].ll>=l&&t[p].rr<=r){
		t[p].val=min(t[p].val,z);t[p].tag=min(t[p].val,z);
		return;
	}
	spread(p);
	int mid=t[p].ll+t[p].rr>>1;
	if(l<=mid)assign(l,r,z,2*p);
	if(r>mid)assign(l,r,z,2*p+1);
	up(p);
}
int main(){
	scanf("%d%d",&n,&m);
	for(register int i(1),x,y;i<=m;++i){
		scanf("%d%d%d",&x,&y,&f[1]);
		v[x].push_back((ed){y,f[1]});
		v[y].push_back((ed){x,f[1]});
	}
	dij(1);ans=f[n];
	memcpy(pre,pr,sizeof(pr));
	for(int i(1);i<=n;++i)tr[pr[i]].push_back(i);
	dfs(1,0,1);
	no2=n;
	while(no2){
		id[no2]=++cnt;no2=pre[no2];
	}
	int u,nn=cnt,x,y,xx,yy;
	cnt=0;
	for(register int i(1);i<=n;++i){
		for(register int j(0);j<v[i].size();++j){
			u=v[i][j].to;//考虑每条边的贡献 ，区间取min 
			if(pre[u]!=i&&pre[i]!=u){
				x=lca(n,u),y=lca(n,i);xx=u,yy=i;
				if(id[x]<id[y])swap(x,y),swap(xx,yy);
				if(id[x]-1>=id[y])me[++cnt].l=id[y],me[cnt].r=id[x]-1,me[cnt].val=v[i][j].val+f[yy]-f[y]+f[xx]+f[n]-f[y];
			}
		}
	}
	sort(me+1,me+cnt+1,cmp);//按赋值从大到小进行赋值操作 
	build(1,nn-1,1);
	for(int i(1);i<=cnt;++i)assign(me[i].l,me[i].r,me[i].val,1),printf("%d %d %d\n",me[i].l,me[i].r,me[i].val);//赋值 
	ans=max(ans,t[1].val);//取全局最大值 
	printf("%d",ans);
	return 0;
}