题目描述
给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出从1号点到n号点的最多经过k条边的最短距离，如果无法从1号点走到n号点，输出impossible。

注意：图中可能存在负权回路。

输入格式
第一行包含三个整数n，m，k。

接下来m行，每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。

输出格式
输出一个整数，表示从1号点到n号点的最多经过k条边的最短距离。

如果不存在满足条件的路径，则输出“impossible”。

数据范围
1≤n,k≤500,
1≤m≤10000,
任意边长的绝对值不超过10000。

样例
输入样例：
3 3 1
1 2 1
2 3 1
1 3 3
输出样例：
3

import java.io.*;
import java.util.*;

class Node {
    int a,b,c;

    public Node(int a, int b, int c) { // 边a表示出点，b表示入点，w表示边的权重
        this.a = a;
        this.b = b;
        this.c = c;
    }
}

public class _853 {
    static  int N = 500,M=100010;
    static  int INF = 0x3f3f3f;
    static  int dist[] = new int[N]; // 从1到点到n号点的距离
    static  int back[] = new int[N]; //备注dist
    static  int n,m,k;
    static  Node []list = new Node[M];

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String str [] = bf.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        k = Integer.parseInt(str[2]);
        for(int i = 0;i < m;i++){
            String  s [] = bf.readLine().split(" ");
            int x = Integer.parseInt(s[0]);
            int y = Integer.parseInt(s[1]);
            int z = Integer.parseInt(s[2]);
            list[i] = new Node(x,y,z);
        }

        bellman_ford();




    }
    // 求1到n的最短路距离，如果无法从1走到n，则返回impossible。
  static   void bellman_ford(){
      Arrays.fill(dist,INF);
      dist[1] = 0;
      for(int i = 0;i < k;i++){
          back = Arrays.copyOf(dist,n+1);// 由于是从1开始存到n
          for(int j = 0;j < m;j++){
              Node node = list[j];
              int a = node.a,b = node.b,c = node.c;
              dist[b] = Math.min(dist[b],back[a] + c);
          }
      }
      System.out.println(dist[n] > INF /2 ? "impossible":dist[n]);



    }
}