K短路，普遍的算法是采用AStar求解，先建立反向边跑一遍dij,或者spfa什么的。跑出反向边的距离就可以看为估价函数中的$h()$。设$dist$为当前已经走过的距离，那么$f(node)=dist+h(son)$,然后跑一遍AStar，根据一些莫名其妙的东西可以得到第$i$次出栈的即为第$i$短路。
//BZOJ 1598
//by Cydiater
//2016.10.25
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <bitset>
#include <string>
#include <algorithm>
#include <iomanip>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define pii pair<int,int>
#define mp make_pair
#define Pii priority_queue<pii,vector<pii>,greater<pii> >
const int MAXN=1e6+5;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,M,K,LINK[MAXN],undis[MAXN],len=0,f[MAXN],cnt[MAXN],ans[MAXN],dis[MAXN];
bool vis[MAXN];
struct edge{
int y,next,v;
}e[MAXN];
Pii Q,q;
namespace solution{
inline void insert(int x,int y,int v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;}
void init(){
N=read();M=read();K=read();
up(i,1,M){
int x=read(),y=read(),v=read();
insert(x,y,v);
insert(y,x,-v);
}
}
void pre_dijkstra(){
memset(vis,0,sizeof(vis));
memset(undis,10,sizeof(undis));
undis[1]=0;Q.push(mp(undis[1],1));
while(!Q.empty()){
pii tmp=Q.top();Q.pop();
int node=tmp.second;
if(vis[node])continue;
vis[node]=1;
for(int i=LINK[node];i;i=e[i].next)
if(undis[e[i].y]>undis[node]-e[i].v&&e[i].v<0){
undis[e[i].y]=undis[node]-e[i].v;
Q.push(mp(undis[e[i].y],e[i].y));
}
}
}
void now_AStar(){
memset(cnt,0,sizeof(cnt));
memset(ans,-1,sizeof(ans));
q.push(mp(undis[N],N));
while(!q.empty()){
pii tmp=q.top();q.pop();
int node=tmp.second;
cnt[node]++;if(node==1)ans[cnt[node]]=tmp.first;
for(int i=LINK[node];i;i=e[i].next)if(cnt[node]<=K&&e[i].v>0)
q.push(mp(tmp.first-undis[node]+e[i].v+undis[e[i].y],e[i].y));
}
}
void slove(){
pre_dijkstra();
now_AStar();
}
void output(){
up(i,1,K)printf("%d\n",ans[i]);
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
slove();
output();
return 0;
}