Description：

给一个带权无向图，选一条边删掉使得从 $1$ 到 $n$ 最短路径最长，输出这个新的最短路径和选择方案数。

$1\le n \le 100000$

Solution：

首先从 $1$ 开始做最短路，求出到每个点的距离 $dis1[k]$ ，然后把从 $1$ 开始的最短路树建出来，那么删掉的边一定在最短路树从 $1$ 到 $n$ 的路径上，无论这个最短路是否唯一，然后再从 $n$ 做一遍最短路，求出从 $k$ 到 $n$ 的最短路 $dis2[k]$ ，我们把整张图重新标号，对于在 $1$ 到 $n$ 路径上的点，把标号设为从 $1$ 开始的深度，对于其他点，设为和 $n$ 的 $LCA$ 的深度，也就是说把从 $1$ 到 $n$ 的最短路搞出来，然后把其他子树的点都压到这条路径上，然后我们用线段树来维护这条路径，线段树每个点的值代表删掉这条边后 $1$ 到 $n$ 的最短路，然后枚举所有的非树边，如果经过边 $(x,y)$ 的最短路1是 $1\to a\to x\to y\to b\to n$ ，其中 $1\to a$ 和 $b\to n$ 在 $1$ 到 $n$ 的最短路上，那么对于 $1$ 到 $n$ 的最短路上 $a$ 和 $b$ 之间的边都存在一种方案删掉这条边而走 $x\to y$ ，考虑这个对线段树维护的信息的影响，会发现这是一个区间取 $min$ 操作，最后 $dfs$ 一遍线段树求最大值就行了，之所以是最大值因为要让最短路径最长，删掉这条道路就能使最短路径最长。其实如果不用求方案数只要维护一个变量就行了。

注意特判所有边都在最短路图上的情况。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXM 200010

#define MAXN 100010

struct edge

{

	int fr,to,nxt,v,id;

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b,int c,int id)

{

	++edgenum;e[edgenum].fr = a;e[edgenum].to = b;e[edgenum].id = id;

	e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].fr = b;e[edgenum].to = a;e[edgenum].id = id;

	e[edgenum].v = c;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return; 

}

int d[2][MAXN];

bool vis[MAXN];

int fa[MAXN];

bool used[MAXM];

int ine[MAXN];

void dijkstra(int s,int type)

{

	memset(vis,false,sizeof(vis));

	memset(d[type],0x3f,sizeof(d[type]));

	d[type][s] = 0;

	fa[s] = 0;

	priority_queue< pair<int,int> > q;

	q.push(make_pair(0,s));

	while(!q.empty())

	{

		int k = q.top().second;q.pop();

		if(vis[k])continue;

		vis[k] = true;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(d[type][e[i].to] > d[type][k] + e[i].v)

			{

				ine[e[i].to] = i;

				d[type][e[i].to] = d[type][k] + e[i].v;

				fa[e[i].to] = k;

				q.push(make_pair(-d[type][e[i].to],e[i].to));

			}

		}

	}

	return;

}

int s[MAXN],top = 0;

int q[MAXN],tot = 0;

int mrk[MAXN];

void dfs(int k)

{

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(mrk[e[i].to] != 0)continue;

		if(fa[e[i].to] != k)continue;

		mrk[e[i].to] = mrk[k];

		dfs(e[i].to);

	}

	return;

}

const int INF = 0x3f3f3f3f;

struct node

{

	int lc,rc;

	int tag;

	node(){tag = INF;}

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void modify(int rt,int L,int R,int k,int l,int r)

{

	if(k >= t[rt].tag)return;

	if(L <= l && r <= R)

	{

		t[rt].tag = k;

		return;

	}

	if(L <= mid)modify(t[rt].lc,L,R,k,l,mid);

	if(R > mid)modify(t[rt].rc,L,R,k,mid + 1,r);

	return;

}

void pushdown(int rt)

{

	if(t[t[rt].lc].tag > t[rt].tag)t[t[rt].lc].tag = t[rt].tag;

	if(t[t[rt].rc].tag > t[rt].tag)t[t[rt].rc].tag = t[rt].tag;

	return;

}

int ans1 = 0,ans2 = 0;

void dfs1(int rt,int l,int r)

{

	if(l == r){ans1 = max(ans1,t[rt].tag);return;}

	pushdown(rt);

	dfs1(t[rt].lc,l,mid);dfs1(t[rt].rc,mid + 1,r);

	return;

}

void dfs2(int rt,int l,int r)

{

	if(l == r){if(t[rt].tag == ans1)++ans2;return;}

	dfs2(t[rt].lc,l,mid);dfs2(t[rt].rc,mid + 1,r);

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	int a,b,c;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		add(a,b,c,i);

	}

	dijkstra(n,1);

	memset(ine,false,sizeof(ine));

	dijkstra(1,0);

	for(int i = n;i != 0;i = fa[i])s[++top] = i;

	while(top > 0)q[++tot] = s[top--];

	for(int i = n;i != 1;i = fa[i])used[e[ine[i]].id] = true;

	memset(mrk,0,sizeof(mrk));

	for(int i = 1;i <= tot;++i)mrk[q[i]] = i;

	for(int i = 1;i <= tot;++i)dfs(q[i]);

	build(root,1,tot - 1);

	for(int i = 1;i <= edgenum;++i)

	{

		if(used[e[i].id])continue;

		if(mrk[e[i].fr] > mrk[e[i].to] - 1)continue;

		int dis = d[0][e[i].fr] + e[i].v + d[1][e[i].to];//cout << mrk[e[i].fr] << " " << mrk[e[i].to] - 1 << " " << dis << endl;

		modify(root,mrk[e[i].fr],mrk[e[i].to] - 1,dis,1,tot - 1);

	}

	dfs1(root,1,tot - 1);dfs2(root,1,tot - 1);

	if(ans1 == d[0][n])ans2 = m;

	cout << ans1 << " " << ans2 << endl;

	return 0;

}