思路

1. 使用一个对列来存储更新过距离的点；
2. 使用队头来更新与他有边的节点
3. 注意入队的时候来更新下标志位 出队的时候也更新下标志位；
4. 其余的都是经典操作 经典的插入操作；经典的遍历操作
5. 注意初始化 -------------最好单独拿出初始化 省的遗漏初始化

import java.util.*;
public class Main{
    static int INF=Integer.MAX_VALUE>>1;
    static int N=100010;
    static int n;
    static int m;

    //邻接表存储图
    static int []h=new int[N];
    static  int []e=new int [N];
    static int []ne=new int[N];
    static int []w=new int[N];
    static int index;
    static int []dist=new int[N];
    static boolean[]st=new boolean[N];
    //队里 用来存储 更新的点；
    static Queue<Integer>q=new LinkedList();
    //经典邻接表插入操作
    static void add(int a,int b,int c){
        w[index]=c;
        e[index]=b;
        ne[index]=h[a];
        h[a]=index++;
    }
    //初始化操作
    static {
        Arrays.fill(h,-1);
        Arrays.fill(dist,INF);
        dist[1]=0;
        q.add(1);
        st[1]=true;
    }

    //spfa套路模板
    static int spfa(){
        //队列不空的时候才进行；
        while(!q.isEmpty()){
            //取出队头节点，并更新其是否更新过为false
            int t=q.poll();
            st[t]=false;
            //经典邻接表遍历操作
            for(int i=h[t];i!=-1;i=ne[i]){
                int j=e[i];
                //如果下一个节点的距离，可以使用当前的节点更新；就更新下一个节点的距离，并更新下一个节点的标志，以及将其入队
                if(dist[j]>dist[t]+w[i]){
                    dist[j]=dist[t]+w[i];
                    if(!st[j]){
                        st[j]=true;
                        q.add(j);
                    }
                }
            }
        }
        return dist[n]==INF?-1:dist[n];
    }

    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        for(int i=1;i<=m;i++){
            add(sc.nextInt(),sc.nextInt(),sc.nextInt());
        }
        int res=spfa();
        if(res==-1){
            System.out.println("impossible");
        }else{
            System.out.println(res);
        }
    }
}