#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=510;

int n,m;
int g[N][N];//稠密图用邻接矩阵
int dist[N];
bool st[N];

// int dijkstra()
// {
//     memset(dist, 0x3f, sizeof dist);
//     dist[1]=0;

//     for(int i=0; i<n; i++)
//     {
//         int t=-2;
//         for(int j=1; j<=n; j++)
//         {
//             if(!st[j] && (t==-2 || dist[t]> dist[j]))
//                 t=j;
//         }

//         if(t==n) break;
//         st[t]=true;

//         for(int j=1; j<=n; j++)
//             dist[j]=min(dist[j], dist[t]+g[t][j]);
//     }

//     if(dist[n]==0x3f3f3f3f) return -1;
//     return dist[n];
// }

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1]=0;


    for(int i=0; i<n; i++)
    {
        int t=-1;
        for(int j=1; j<=n; j++)
        {
            if(!st[j] && (t==-1 || dist[t]> dist[j]))
                t=j;
        }

        st[t]=true;
        if(t==n) break;

        for(int j=1; j<=n; j++)
            dist[j]=min(dist[j], dist[t]+g[t][j]);

    }

    if(dist[n]=0x3f3f3f3f) return -1;
    return dist[n];

}

int main()
{
    cin>>n>>m;

    memset(g, 0x3f, sizeof g);

    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b]=min(g[a][b], c);
    }

    int t=dijkstra();

    printf("%d\n", t);

    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100010;

int n,m;
int h[N],e[N],ne[N],idx;
int q[N],d[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bool topsort()
{
    int hh=0,tt=-1;

    for(int i=1;i<=n;i++)
        if(!d[i])
        {
            q[++tt]=i;
        }

    while(hh<=tt)
    {
        int t=q[hh++];

        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            d[j]--;
            if(d[j]==0) q[++tt]=j;
        }
    }
    return tt==n-1;
}

int main()
{
    cin>>n>>m;

    memset(h,-1,sizeof h);

    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        d[b]++;
    }

    if(topsort())
    {
        for(int i=0;i<n;i++) printf("%d ",q[i]);
        puts("");
    }else
    {
        puts("-1");
    }

    return 0;
}

#include<iostream>
#include<cstring>

using namespace std;

const int N=100010;

int n,m;
int h[N],e[N],ne[N],idx;
int d[N],q[N];//d存放距离，q是数组模拟队列

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int bfs()
{
    int hh=0,tt=0;
    q[0]=1;//把1号顶点入队

    memset(d,-1,sizeof d);

    d[1]=0;
    while(hh<=tt){
        int t=q[hh++];//hh指向对头，tt指向队尾的元素
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(d[j]==-1){
                d[j]=d[t]+1;
                q[++tt]=j;//j入队
            }
        }
    }
    return d[n];
}

int main(){

    cin>>n>>m;
    memset(h,-1,sizeof h);

    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }

    cout<<bfs()<<endl;
    return 0;
}

// #include<iostream>
// #include<algorithm>
// #include<cstring>
// using namespace std;

// const int N=100010,M=N*2;

// int n;//树的节点数
// int h[N],e[M],ne[M],idx;//邻接表，所谓的链式前向星，h是头结点，e是边，ne是下一条边，idx是当前第一个空余位置
// bool st[N];

// int ans=N;

// void add(int a,int b)
// {
//     //头插法，先把b装进去，再把ne[idx]插到h[a]的头部，然后idx后移一位
//     e[idx]=b,ne[idx]=h[a],h[a]=idx++;

// }

// //返回以u为根的子树中点的数量
// int dfs(int u){
//     st[u]=true;

//     int sum=1,res=0;//sum放u点为根的子树的顶点的数量，目的是为了求n-sum 那个块
//     // res为u的子树（不包含u）中顶点数量的最大值
//     for(int i=h[u];i!=-1;i=ne[i])
//     {
//         int j=e[i];
//         if(!st[j]){
//             int s=dfs(j);
//             res=max(res,s);//在邻接的所有子树中找一个最大的
//             sum+=s;
//         }
//     }
//     //求sum的目的就是为了求n-sum,n-sum是u这个点所在的子树点的总和
//     res=max(res,n-sum);//res应该是最终的题中所求
//     ans=min(ans,res);//ans是全局变量，每次取最小值
//     return sum;
// }

// int main()
// {
//     cin>>n;
//     memset(h,-1,sizeof h);

//     for(int i=0;i<n;i++)
//     {
//         int a,b;
//         cin>>a>>b;
//         add(a,b),add(b,a);
//     }

//     //从第一个点开始遍历，所有的点都被去一遍，然后算一把
//     dfs(1);
//     cout<<ans<<endl;
//     return 0;
// }

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=100010, M=N*2;

int n;//树中节点数
int h[N],e[M], ne[M], idx;
bool st[N];

int ans=N;

void add(int a, int b)
{
    //头插法
    e[idx]=b, ne[idx]=h[a], h[a]=idx++;
}

//返回以u为根的子树的点的数量，包含u
int dfs(int u)
{
    st[u]=true;

    int sum=1, res=0;// n-sum, res存子树不含u中顶点数量的最大值
    for(int i=h[u]; i!=-1; i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            int s=dfs(j);
            res=max(res, s);
            sum+=s;
        }
    }

    res=max(res, n-sum);
    ans=min(ans, res);
    return sum;
}

int main()
{
    cin>>n;
    memset(h, -1, sizeof h);

    for(int i=0; i<n; i++)
    {
        int a, b;
        scanf("%d%d",&a, &b);
        add(a,b), add(b,a);
    }

    dfs(1);
    cout<<ans<<endl;

    return 0;
}


// #include<iostream>
// #include<algorithm>
// #include<cstring>

// using namespace std;

// const int N=100010, M=2*N;

// int n;
// int h[N], e[M], ne[M], idx;
// bool st[N];

// int ans=N;

// void add(int a,int b)
// {
//     e[idx]=b, ne[idx]=h[a], h[a]=idx++;
// }

// int dfs(int u)
// {
//     st[u]=true;

//     int sum=1, res=0;

//     for(int i=h[u]; i!=-1; i=ne[i])
//     {
//         int j=e[i];
//         if(!st[j])
//         {
//             int s=dfs(j);
//             res=max(res,s);
//             sum+=s;
//         }
//     }

//     res=max(res, n-sum);
//     ans=min(ans, res);
// }

// int main()
// {
//     cin>>n;
//     memset(h, -1, sizeof h);

//     for(int i=0; i<n; i++)
//     {
//         int a,b;
//         cin>>a>>b;
//         add(a,b), add(b,a);
//     }

//     dfs(1);
//     cout<<ans<<endl;
//     return 0;
// }

// //把二维状态转化为一个一维的字符串，然后每个一维的字符串
// //在bfs时进行转移，就是看看谁先到达终止的目标状态
// #include<iostream>
// #include<algorithm>
// #include<unordered_map>
// #include<queue>

// using namespace std;

// int bfs(string state)
// {
//     queue<string> q;//用string存每个状态
//     unordered_map<string, int> d;//存每个状态到起始状态的最近距离，也就是操作次数 

//     q.push(state);
//     d[state]=0;

//     int dx[4]={-1, 0, 1, 0}, dy[4]={0, 1, 0, -1};

//     string end="12345678x";
//     while(q.size())
//     {
//         auto t=q.front();
//         q.pop();

//         if(t==end) return d[t];

//         int distance=d[t];
//         int k=t.find('x');
//         int x=k/3, y=k%3; //转化为二维坐标
//         //状态转移
//         for(int i=0; i<4; i++)
//         {
//             int a=x+dx[i], b=y+dy[i];
//             if(a>=0 && a<3 && b>=0 && b<3)
//             {
//                 //交换操作
//                 swap(t[a*3+b], t[k]);//在一维数组中进行
//                 if(!d.count(t))//如果这个状态没有被计算过
//                 {
//                     d[t] = distance + 1;
//                     q.push(t);
//                 }

//                 swap(t[a*3+b], t[k]);//再给人家换回来，下一个循环还要用原来的状态呢
//             }
//         }
//     }

//     //如果最后没有遇到end
//     return -1;
// }

// int main()
// {
//     char s[2];

//     string state;
//     for(int i=0; i<9; i++) 
//     {
//         cin>>s;
//         state+=*s;
//     }

//     cout<<bfs(state)<<endl;

//     return 0;

// }


#include<iostream>
#include<queue>
#include<unordered_map>
#include<algorithm>

using namespace std;

int bfs(string state)
{
    string end="12345678x";
    unordered_map<string, int> d;
    queue<string> q;

    q.push(state);
    d[state]=0;
    int dx[4]={-1, 0, 1, 0}, dy[4]={0, 1, 0, -1};
    while(q.size())
    {
        string t=q.front();
        q.pop();

        if(t==end) return d[t];

        int distance=d[t];
        int k=t.find('x');
        int x=k/3, y=k%3;
        for(int i=0; i<4; i++)
        {
            int a=x+dx[i], b=y+dy[i];
            if(a>=0 && a<3 &&b>=0 && b<3)
            {
                swap(t[k], t[a*3+b]);
                if(!d.count(t))
                {
                    d[t]=distance+1;
                    q.push(t);
                }
                swap(t[k], t[a*3+b]);
            }
        }

    }

    return -1;
}

int main()
{
    char s[2];

    string state;
    for(int i=0; i<9; i++)
    {
        cin>>s;
        state+=*s;
    }

    cout<<bfs(state) <<endl;

    return 0;

}

// //当不让使用unorder_map的时候，就只能手动进行字符串哈希了
// #include<bits/stdc++.h>

// using namespace std;

// typedef unsigned long long ULL;

// const int M=1e7;
// const int N=100010, P=13331;

// ULL h[N];//存放字符串的前缀值
// int d[M];

// //标准的字符串哈希
// ULL hash_CSM(string a)
// {
//     h[0]=0;
//     for(int i=1; i<=9; i++)
//     {
//         h[i]=h[i-1]*P + (a[i-1]-'0'+1);
//     }

//     return h[9]%M;//hash用ULL实现的时候会自动取余，
//     // 但是此题hash值需要作为数组下标，对该结点进行标记，所以通过多次试验，找到M可实现不冲突，且数组可开辟这些空间

// }

// int bfs(string state)
// {
//     queue<string> q;

//     q.push(state);
//     d[hash_CSM(state)]=0;
//     string end="12345678x";
//     int dx[4]={-1, 0, 1, 0}, dy[4]={0, 1, 0, -1};
//     while(q.size())
//     {
//         string t=q.front();
//         q.pop();

//         if(t==end) return d[hash_CSM(t)];

//         int distance=d[hash_CSM(t)];
//         int k=t.find('x');
//         int x=k/3, y=k%3;
//         for(int i=0; i<4; i++)
//         {
//             int a=x+dx[i];
//             int b=y+dy[i];
//             if(a>=0 &&a<3 &&b>=0 &&b<3)
//             {
//                 swap(t[a*3+b], t[k]);
//                 if(!d[hash_CSM(t)])
//                 {
//                     d[hash_CSM(t)]=distance+1;
//                     q.push(t);
//                 }

//                 swap(t[a*3+b], t[k]);
//             }
//         }
//     }

//     return -1;
// }

// int main()
// {
//     string state;

//     char s[2];//自动过滤回车换行制表等无效操作
//     for(int i=0; i<9;i++)
//     {
//         cin>>s;
//         state+=*s;
//     }

//     cout<< bfs(state) <<endl;

//     return 0;

// }

// #include<iostream>

// using namespace std;

// const int N=10;

// //存放路径
// int path[N];
// bool st[N];//记录是否被使用过
// int n;

// //计算u->n所经过的路径,根节点是第0层，一直存到n-1层
// void dfs(int u)
// {
//     if(u==n)
//     {
//         for(int i=0; i<n; i++) printf("%d ",path[i]);
//         puts("");
//         return;
//     }
//     else
//     {
//         for(int i=1; i<=n; i++)//枚举这n个数
//         {
//             if(!st[i])
//             {
//                 path[u]=i;
//                 st[i]=true;
//                 dfs(u+1);
//                 path[u]=0;//画个树就知道为啥要恢复现场了
//                 st[i]=false;
//             }
//         }
//     }

// }

// int main()
// {
//     scanf("%d",&n);
//     dfs(0);

//     return 0;
// }

// //y总玩降维打击了，直接用状态压缩了，用一个二进制数表示n个状态
// #include<iostream>

// using namespace std;

// const int N=10;

// int n;
// int path[N];

// //n个数，表示成n位的二进制数，访问过对应位置就是1
// //没有访问过，对应位置就是0
// //输出从u->n的路径，state的二进制表示中为1的位置表示这个数被访问过了
// void dfs(int u, int state)
// {
//     if(u==n)
//     {
//         for(int i=0; i<n; i++) printf("%d ", path[i]);
//         puts("");
//         return;
//     }

//     for(int i=0; i<n; i++)
//     {
//         if(!(state>>i & 1))//如果state右移i位的位置上的数为0
//         {
//             path[u]=i+1;
//             dfs(u+1, state+(1<<i));//标记为访问过
//             //这样就不用恢复现场了,因为进入递归的数是
//             // state+(1<<i),也就是state本身并没有变，下次
//             // for循环用到的state也没有变，所以不用变，递归完成后
//             // 和递归完成前的state的状态是一样的
//         }
//     }
// }

// int main()
// {
//     scanf("%d",&n);

//     //从第0层开始，state初始状态为0，表示n个位置上都为0，都没有被访问过
//     dfs(0, 0);

//     return 0;
// }

#include<iostream>

using namespace std;

const int N=10;

int n;
int path[N];
bool st[N];

void dfs(int u)
{
    if(u==n)
    {
        for(int i=0; i<n ;i++) printf("%d ", path[i]);
        puts("");
        return;
    }

    for(int i=1; i<=n ;i++)
    {
        if(!st[i])
        {
            st[i]=true;
            path[u]=i;
            dfs(u+1);
            st[i]=false;
            path[u]=0;
        }
    }
}

int main()
{
    scanf("%d", &n);
    dfs(0);//从第0层开始

    return 0;
}

#include<iostream>
#include<algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N=50010;

int n;
PII cow[N];

//按照wi+si从小到大排序
int main()
{
    scanf("%d", &n);
    for(int i=0; i<n; i++)
    {
        int w,s;
        scanf("%d%d", &w, &s);
        cow[i]={w+s, w};//太妙了，利用一个pair就可以全解决了
    }

    sort(cow, cow+n);

    int res=-2e9, sum=0;
    for(int i=0; i< n; i++)
    {
        int w=cow[i].second, s=cow[i].first-w;
        res=max(res, sum-s);
        sum+=w;
    }

    printf("%d\n", res);
    return 0;

}

//据说是绝对值不等式，选中位数的时候的，距离和最小
//因为把距离转化成绝对值形式表示，第一个和倒数第一个
//第二个和倒数第二个.....中位数看成一组，选取的点在
// 一组两个端点中间的时候，总和最小，所以在这些组的中间的唯一的点的
// 只有一个中位数。如果是偶数个点的话，选中间两个点间任意一个点就行
#include<iostream>
#include<algorithm>
using namespace std;

const int N=100010;

int n;
int a[N];

int main()
{
    scanf("%d",&n);
    for(int i=0; i<n;i++) scanf("%d", &a[i]);

    sort(a, a+n);

    int res=0;
    for(int i=0; i<n ; i++) res+=abs(a[i]-a[n/2]);

    printf("%d\n", res);
    return 0;
}

//贪心，谁话费的时间短谁就先来，反证法可以证明
//俗称排序原理，或者排序不等式
// 排序不等式表述如下，设有两组数a1,a2,……an和b1,b2,……bn，
// 满足a1≤a2≤……≤an,b1≤b2≤……≤bn，c1,c2,……cn是b1,b2,……bn的乱序排列，
// 则有a1bn+a2bn-1+……+anb1≤a1c1+a2c2+……+ancn≤a1b1+a2b2+……+anbn,
// 当且仅当a1=a2=……=an或b1=b2=……=bn时等号成立。一般为了便于记忆，
// 常记为：反序和≤乱序和≤顺序和.
#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;

const int N=100010;

int n;
int t[N];

int main()
{
    scanf("%d",&n);
    for(int i=0; i<n; i++) scanf("%d",&t[i]);

    sort(t, t+n);

    LL res=0;
    for(int i=0; i< n;i++) res+= t[i]*(n-i-1);

    printf("%lld\n", res);

    return 0;
}

//最先开始合并的果子，被计算的次数最多
//所以我们尽量要先合并重量小的果子
//这里用小根堆是真的秀！！
#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

int main()
{
    int n;
    scanf("%d",&n);

    priority_queue<int, vector<int>, greater<int> > heap;
    while(n--)
    {
        int x;
        scanf("%d", &x);
        heap.push(x);
    }

    int res=0;
    while(heap.size()>1)
    {
        int a=heap.top(); heap.pop();
        int b=heap.top(); heap.pop();
        res+=a+b;
        heap.push(a+b);
    }

    printf("%d\n", res);
    return 0;

}