https://www.luogu.com.cn/problem/P9981
首先显而易见的是第一问的答案用拓扑排序，然后用它的倒序进行DP。我们考虑第二问。
首先要保证第一问的情况下才能考虑第二问，于是我们对于所有点按照第一问的答案分层，先按照新加入的边考虑，再按照上一层点的排名考虑，做完这一层后直接对这一层排序，rank用于下一层。
由于每层的个数相加是 \(n\)，所以复杂度小于 \(O(m+n\log n)\)。
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=200010,M=400010;
struct temp{
int a,b,c;
bool operator<(const temp&B)const{
return a<B.a||a==B.a&&b<B.b;
}
}tmp[N];
int n,m,h[N],e[M],ne[M],w[M],idx,q[N],in[N],f[N],rk[N];
long long ans[N];
vector<int>g[N];
void add(int a,int b,int c){
++in[b],e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void topo(){
int hh=0,tt=0;
for(int i=1;i<=n;++i)
if(!in[i])q[tt++]=i;
while(hh!=tt){
int t=q[hh++];
for(int i=h[t];~i;i=ne[i]){
int j=e[i];
--in[j];
if(!in[j])q[tt++]=j;
}
}
}
void dp(){
for(int i=n-1;~i;--i){
int x=q[i];
for(int ii=h[x];~ii;ii=ne[ii]){
int j=e[ii];
f[x]=max(f[x],f[j]+1);
}
g[f[x]].push_back(x);
}
}
int main(){
#ifdef LOCAL
freopen("1.txt","r",stdin);
#endif
#ifndef LOCAL
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
#endif
cin>>n>>m;
memset(h+1,-1,n*4);
for(int i=1;i<=m;++i){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
// return 0;
topo();
dp();
for(int t=1;t<n&&!g[t].empty();++t){
int tot=0;
for(int x:g[t]){
int mn=0,to=0;
for(int i=h[x];~i;i=ne[i]){
int j=e[i];
if(f[j]!=f[x]-1)continue;
if(!to||mn>w[i]||(mn==w[i]&&rk[j]<rk[to])){
to=j;
mn=w[i];
}
}
ans[x]=mn+ans[to];
tmp[++tot]={mn,rk[to],x};
}
sort(tmp+1,tmp+1+tot);
for(int i=1;i<=tot;++i)rk[tmp[i].c]=i;
}
for(int i=1;i<=n;++i)
cout<<f[i]<<' '<<ans[i]<<'\n';
return 0;
}