题目大意：

找一条边删除使得从 $1$ 到 $n$ 的最短路最长，问最长的最短路的长度以及有多少种删边的方案。

思路：

这是一道很经典的删边最短路问题。首先，肯定是删除最短路上的边能使最短路更长。我们可以采用找一些边去替换最短路上的边的方法，但是有个问题就是找到的边连接的两个点可能不在最短路上。我们需要找到需要用这条边的路径，设这条边为从 $x$ 到 $y$，那么用上这条边的最短路径长度为 $d1_{x}+dn_{y}+w$，$w$ 是这条边的边权，$d1$ 是从 $1$ 出发的最短路数组，$dn$ 是从 $n$ 出发的最短路数组。考虑这个路径能用于那些最短路上的边被删，我们可以找到距离这条边上的两个点距离最近的编号最大和编号最小的两个点，可以发现找出的最短路上的两个点之间的边就是可以代替的边。最后用线段树维护下每条最短路上的边删掉后的答案，每条不是最短路上的边能代替的边，更新这个区间最小值即可。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1e16;
const int N=5e5+5;
struct node{
	int x,y,z,flag;
}a[N];
struct Tree{
	int l,r;
	ll c,lazy;
}tree[4*N];
vector<pair<int,int>>e[N];
ll d1[N],d2[N];
int n,p[N],tot,id[N],l[N],r[N];
bool v[N];
void dij(int st,ll *d){
	for(int i=1;i<=n;i++){
		d[i]=inf;
		v[i]=0;
	}
	priority_queue<pair<ll,int>>q;
	q.push(make_pair(0,st));
	d[st]=0;
	while(!q.empty()){
		int x=q.top().second;
		q.pop();
		if(v[x])continue;
		v[x]=1;
		for(int i=0;i<e[x].size();i++){
			int y=e[x][i].first;
			ll z=a[e[x][i].second].z;
			if(d[y]>d[x]+z){
				d[y]=d[x]+z;
				q.push(make_pair(-d[y],y));
			}
		}
	}
}
void js1(){
	int x=1;
	p[++tot]=1;
	id[1]=1;
	while(x!=n){
		for(int i=0;i<e[x].size();i++){
			int y=e[x][i].first;
			ll z=a[e[x][i].second].z;
			if(d1[x]+z+d2[y]==d1[n]){
				a[e[x][i].second].flag=1;
				x=y;
				break;
			}
		}
		p[++tot]=x;
		id[x]=tot;
	}
}
void bfs(int st,int *g,ll *d){
	queue<int>q;
	q.push(p[st]);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		g[x]=st;
		for(int i=0;i<e[x].size();i++){
			int y=e[x][i].first;
			ll z=a[e[x][i].second].z;
			if(d[x]+z!=d[y]||g[y]||id[y])continue;
			q.push(y);
		}
	}
}
void js2(){
	for(int i=1;i<=tot;i++){
		bfs(i,l,d1);
	}
	for(int i=1;i<=tot;i++){
		bfs(i,r,d2);
	}
}
void pushup(int x){
	tree[x].c=min(tree[2*x].c,tree[2*x+1].c);
}
void pushdown(int x){
	tree[2*x].c=min(tree[2*x].c,tree[x].lazy);
	tree[2*x].lazy=min(tree[2*x].lazy,tree[x].lazy);
	tree[2*x+1].c=min(tree[2*x+1].c,tree[x].lazy);
	tree[2*x+1].lazy=min(tree[2*x+1].lazy,tree[x].lazy);
	tree[x].lazy=inf;
}
void build(int x,int l,int r){
	tree[x].l=l;
	tree[x].r=r;
	tree[x].lazy=inf;
	if(l==r){
		tree[x].c=inf;
		return ;
	}
	int mid=(l+r)/2;
	build(2*x,l,mid);
	build(2*x+1,mid+1,r);
	pushup(x);
}
void update(int x,int l,int r,ll k){
	if(tree[x].l>r||tree[x].r<l){
		return ;
	}
	if(tree[x].l>=l&&tree[x].r<=r){
		tree[x].lazy=min(tree[x].lazy,k);
		tree[x].c=min(tree[x].c,k);
		return ;
	}
	if(tree[x].lazy!=inf){
		pushdown(x);
	}
	update(2*x,l,r,k);
	update(2*x+1,l,r,k);
	pushup(x);
}
ll query(int x,int u){
	if(tree[x].l>u||tree[x].r<u){
		return inf;
	}
	if(tree[x].l==tree[x].r){
		return tree[x].c;
	}
	if(tree[x].lazy!=inf){
		pushdown(x);
	}
	return min(query(2*x,u),query(2*x+1,u));
}
void solve(){
	for(int i=1;i<=n;i++){
		if(!l[i])continue;
		for(int j=0;j<e[i].size();j++){
			int y=e[i][j].first;
			ll z=a[e[i][j].second].z;
			if(a[e[i][j].second].flag||l[i]>=r[y]||!r[y])continue;
			update(1,l[i],r[y]-1,d1[i]+d2[y]+z);
		}
	}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		e[x].push_back(make_pair(y,i));
		e[y].push_back(make_pair(x,i));
		a[i]={x,y,z,0};
	}
	dij(1,d1);
	dij(n,d2);
	js1();
	js2();
	build(1,1,tot);
	solve();
	ll ans=0;
	int c=0;
	for(int i=1;i<=m;i++){
		ll res=d1[n];
		if(a[i].flag){
			res=query(1,min(id[a[i].x],id[a[i].y]));
		}
		if(res>ans){
			ans=res;
			c=1;
		}else if(res==ans){
			c++;
		}
	}
	cout<<ans<<" "<<c<<"\n";
	return 0;
}