K短路居然用A*……奇妙。
先建反图从终点（1）跑一遍最短路，再A*，用堆存当前点到终点距离+从起点到当前点距离。
每次取出终点都可以视为发现了一个新的最短路。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<queue>
#define maxn 1020
#define maxm 10020
using namespace std;
inline long long read(){
long long num=,f=;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-;
ch=getchar();
}
while(isdigit(ch)){
num=num*+ch-'';
ch=getchar();
}
return num*f;
} struct Node{
int pnt,dis;
bool operator <(const Node a)const{
return dis<a.dis;
}
bool operator ==(const Node a)const{
return dis==a.dis;
}
bool operator <=(const Node a)const{
return dis<=a.dis;
}
}; struct Heap{
Node heap[maxn*];
int size;
Heap(){size=;}
inline void push(Node x){
heap[++size]=x;
register int i=size,k;
while(i>){
k=i>>;
if(heap[k]<=heap[i]) return;
swap(heap[k],heap[i]);
i=k;
}
}
inline Node pop(){
Node ans=heap[]; heap[]=heap[size--];
register int i=,k;
while((i<<)<=size){
k=i<<;
if(k<size&&heap[k|]<heap[k]) k|=;
if(heap[i]<=heap[k]) return ans;
swap(heap[k],heap[i]);
i=k;
}
return ans;
}
}s; int ans[maxn],cnt;
int dis[maxn];
bool vis[maxn]; struct Picture{
struct Edge{
int next,to,val;
}edge[maxm*];
int head[maxn],num;
Picture(){memset(vis,,sizeof(vis));num=;memset(head,,sizeof(head));}
inline void add(int from,int to,int val){
edge[++num]=(Edge){head[from],to,val};
head[from]=num;
}
void prepare(int Start){
memset(dis,/,sizeof(dis)); dis[Start]=;
queue<int>q; q.push(Start);
while(!q.empty()){
int from=q.front();q.pop();
vis[from]=;
for(int i=head[from];i;i=edge[i].next){
int to=edge[i].to;
if(dis[to]<=dis[from]+edge[i].val) continue;
dis[to]=dis[from]+edge[i].val;
if(vis[to]) continue;
vis[to]=; q.push(to);
}
}
return;
}
void Astar(int Start,int tme){
s.push((Node){Start,dis[Start]});
while(s.size){
Node from=s.pop();
int x=from.pnt,dst=from.dis;
if(x==) ans[++cnt]=dst;
if(tme==cnt) return;
for(int i=head[x];i;i=edge[i].next){
int to=edge[i].to;
s.push((Node){to,dst-dis[x]+edge[i].val+dis[to]});
}
}
}
}Pre,Sub; int main(){
memset(ans,-,sizeof(ans));
int n=read(),m=read(),e=read();
for(int i=;i<=m;++i){
int x=read(),y=read(),z=read();
if(x<y) swap(x,y);
Pre.add(x,y,z);
Sub.add(y,x,z);
}
Sub.prepare();
Pre.Astar(n,e);
for(int i=;i<=e;++i) printf("%d\n",ans[i]);
return ;
}