首先找出任意一条1～n的最短路径。显然删除的边只有在该最短路上才会对最短路长度产生影响。
不会证明地给出一个找不到反例的结论：删除一条边后，新图中一定有一条1～n的最短路径上存在一条边x->y，满足在原图中1～x的最短路和y～n的最短路上该删除边均不是必经边。
另一个显然的结论是，原图中经过边x->y情况下的最短路一定可以描述为1->l->x->y->r->n，其中l和r是之前找出的最短路上的两个点。因为如果在到达x之前在最短路上反复横跳，不如直接走原最短路。后者同理。
由两个结论容易发现，要考虑原问题，只需要枚举一条边x->y，求出l为1->x的最短路和1->n的最短路最早分离点，及r为y->n和1->n最短路的最晚重合点，用该路径长度更新原最短路上l～r这段区间的边被删除后的答案即可。在最短路dag上随便dp一下，线段树或者并查集实现区间更新即可。
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000010
#define N 100010
#define M 400010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}
int n,m,p[N],t,d[N],point[N],id[N],degree[N],pos[N],D[2][N],f[2][N],tree[N<<2],qwq,mx,cnt;
bool flag[N],tag[M];
struct data{int to,nxt,len;
}edge[M];
void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;}
struct data2
{int x,d;bool operator <(const data2&a) const{return d>a.d;}
};
priority_queue<data2> q;
void dijkstra(int start)
{while (!q.empty()) q.pop();memset(d,60,sizeof(d));d[start]=0;memset(flag,0,sizeof(flag));q.push((data2){start,0});for (;;){while (!q.empty()&&flag[q.top().x]) q.pop();if (q.empty()) break;data2 x=q.top();q.pop();flag[x.x]=1;for (int i=p[x.x];i;i=edge[i].nxt)if (x.d+edge[i].len<d[edge[i].to]){d[edge[i].to]=x.d+edge[i].len;q.push((data2){edge[i].to,d[edge[i].to]});}}
}//求start到所有点的单源最短路
void topsort()
{int head=0,tail=0;for (int i=1;i<=n;i++)for (int j=p[i];j;j=edge[j].nxt)if (d[i]+edge[j].len==d[edge[j].to]) degree[edge[j].to]++;for (int i=1;i<=n;i++) if (!degree[i]) id[++tail]=i;while (tail<n){int x=id[++head];for (int i=p[x];i;i=edge[i].nxt)if (d[x]+edge[i].len==d[edge[i].to]){degree[edge[i].to]--;if (!degree[edge[i].to]) id[++tail]=edge[i].to;}}
}//按最短路DAG拓扑排序
void canarrive(int u)
{memset(flag,0,sizeof(flag));flag[u]=1;for (int i=n;i>=1;i--){int x=id[i];for (int j=p[x];j;j=edge[j].nxt)if (d[x]+edge[j].len==d[edge[j].to])flag[x]|=flag[edge[j].to];}
}//判断每个点是否能到终点
void dfs(int k)
{point[qwq++]=k;for (int i=p[k];i;i=edge[i].nxt)if (d[k]+edge[i].len==d[edge[i].to]&&flag[edge[i].to]){tag[i+1>>1]=1;dfs(edge[i].to);break;}
}//找出S到T的任意最短路
void getpos()
{memset(pos,60,sizeof(pos));for (int i=0;i<=qwq;i++) pos[point[i]]=i;
}//求出每个点在最短路链中的位置
void getfirst(int op)
{memset(f[op],60,sizeof(f[op]));for (int i=1;i<=n;i++) D[op][i]=d[i];for (int i=1;i<=n;i++){int x=id[i];if (pos[x]<=qwq) f[op][x]=min(f[op][x],pos[x]);for (int j=p[x];j;j=edge[j].nxt)if (d[x]+edge[j].len==d[edge[j].to]&&!tag[j+1>>1]) f[op][edge[j].to]=min(f[op][edge[j].to],f[op][x]);}
}//求出到每个点的最短路最早从哪个点分离 顺便记最短路
void cover(int k,int l,int r,int x,int y,int p)
{if (l==x&&r==y) {tree[k]=min(tree[k],p);return;}int mid=l+r>>1;if (y<=mid) cover(k<<1,l,mid,x,y,p);else if (x>mid) cover(k<<1|1,mid+1,r,x,y,p);else cover(k<<1,l,mid,x,mid,p),cover(k<<1|1,mid+1,r,mid+1,y,p);
}
void dfs_tree(int k,int l,int r)
{tree[k]=min(tree[k],tree[k>>1]);if (l==r){if (tree[k]==mx) cnt++;else if (tree[k]>mx) mx=tree[k],cnt=1;return;}dfs_tree(k<<1,l,l+r>>1);dfs_tree(k<<1|1,(l+r>>1)+1,r);
}
signed main()
{
#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);
#endifn=read(),m=read();for (int i=1;i<=m;i++){int x=read(),y=read(),z=read();addedge(x,y,z),addedge(y,x,z);}dijkstra(1);topsort();canarrive(n);point[0]=1;dfs(1);qwq--; getpos();getfirst(0);dijkstra(n);topsort();reverse(point,point+qwq+1);getpos();getfirst(1);for (int i=1;i<=n;i++) f[1][i]=qwq-f[1][i];memset(tree,60,sizeof(tree));for (int i=1;i<=n;i++) for (int j=p[i];j;j=edge[j].nxt)if (!tag[j+1>>1]){int x=i,y=edge[j].to;if (f[0][x]<f[1][y]){cover(1,1,qwq,f[0][x]+1,f[1][y],D[0][x]+edge[j].len+D[1][y]);}}dfs_tree(1,1,qwq);if (mx==d[1]) cout<<mx<<' '<<m<<endl;else cout<<mx<<' '<<cnt<<endl;return 0;//NOTICE LONG LONG!!!!!
}
