dij：

#define rep(i,h,t) for (int i=h;i<=t;i++)
const int N=1e4;
struct re{
    int a,b,c;
    bool operator <(const re x) const{
        return b>x.b;
    }
}a[N];
int n,m;
vector<re> ve[N];
bool vis[N];
int dis[N];
priority_queue<re> Q;
int solve()
{
    rep(i,1,n) ve[i].clear();
    rep(i,1,m)
    {
        ve[a[i].a].push_back({a[i].b,a[i].c});
        ve[a[i].b].push_back({a[i].a,a[i].c});
    }
    rep(i,1,n) dis[i]=1e9,vis[i]=0;
    Q.push({1,0}); dis[1]=0;
    while (!Q.empty())
    {
         int x=Q.top().a; Q.pop();
         if (vis[x]) continue; vis[x]=1;
         for (auto v:ve[x])
         {
             if (dis[v.a]>dis[x]+v.b)
             {
                 dis[v.a]=dis[x]+v.b;
                 Q.push({v.a,dis[v.a]});
             }
         }
    }
    return dis[n];
}