package algospot;
import java.util.*;
class Edge implements Comparable<Edge>{
    int x;
    int y;
    int c;
    Edge(int x, int y, int c) {
        this.x=x;
        this.y=y;
        this.c=c;
    }
    @Override
    public int compareTo(Edge e) {
        // TODO Auto-generated method stub
        if(this.x > e.x)
            return 1;
        else if (this.x < e.x)
            return -1;
        else {
            if(this.y > e.y)
                return 1;
            else if (this.y < e.y)
                return -1;
            return 0;
        }
    }

}

public class Move {
    static PriorityQueue<Edge> q;
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int C=sc.nextInt();
        while(C-->0){
            int N=sc.nextInt();
            int M=sc.nextInt();
            q=new PriorityQueue<>();
            for(int i=0;i<M;i++)
                q.add(new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt()));
            System.out.println(run(N,M));           
        }
        sc.close();
    }
    static int run(final int N, final int M) {
        int dist[]=new int[N];
        dist[0]=0;
        for(int i=1;i<N;i++)
            dist[i]=Integer.MAX_VALUE;

        while(!q.isEmpty()){
            Edge tmp=q.poll();
            int len = dist[tmp.x] + tmp.c;
            if( len < dist[tmp.y] || dist[tmp.y] == Integer.MAX_VALUE) 
                dist[tmp.y]=len;
        }
        return dist[N-1];
    }
}