F. Traveling

Solution

构造题，注意细节。
考虑怎么样构造用的边数最少，然后如果m更大就加一些不影响任何最短路的边，如果两两连边还是不够m条就输出No。
首先考虑直接从1到n的最短路，显然必须有$d[1]=d[n]=min\{d[i]\}d[1]=d[n]=min\backslash \{d[i]\backslash \}$。
怎么用最少的边来构造呢？首先1到n我们直接连长度为$d[n]d[n]$的边，然后考虑$2\sim n-12\backslash sim\; n-1$的所有点，将这些点按$dd$从小到大排序。
顺着考虑这些点，如果$d[i]\equiv d[n](\mathrm{m}\mathrm{o}\mathrm{d}2)d[i]\backslash equiv\; d[n]\backslash pmod\; 2$，那么我们只需要添加连接1和$ii$的边，边权为${\displaystyle \frac{d[i]-d[n]}{2}}\backslash dfrac\{d[i]-d[n]\}\{2\}$。
比较麻烦的是如果$d[i]\equiv ̸d[n](\mathrm{m}\mathrm{o}\mathrm{d}2)d[i]\backslash not\backslash equiv\; d[n]\backslash pmod\; 2$，考虑添加两条边，分别是连接1和$ii$的边、连接$ii$和$nn$的边，边权如何确定？设两条边权分别为$a,ba,b$，我们希望走的路径是从1直接走到$ii$再直接走到$nn$，那么就不能出现从1走到$nn$再走到$ii$，或者从$ii$走到1再走到$nn$的情况，为了保证这一点就需要$a+d[n]\ge ba+d[n]\backslash ge\; b$且$b+d[n]\ge ab+d[n]\backslash ge\; a$，也就是我们需要$\mid a-b\mid \backslash left|a-b\backslash right|$尽量小，因此考虑$a=\lfloor {\displaystyle \frac{d[i]}{2}}\rfloor ,b=\lceil {\displaystyle \frac{d[i]}{2}}\rceil a=\backslash left\backslash lfloor\backslash dfrac\{d[i]\}\{2\}\backslash right\backslash rfloor,b=\backslash left\backslash lceil\backslash dfrac\{d[i]\}\{2\}\backslash right\backslash rceil$，如果此时不满足$d[n]\ge b-ad[n]\backslash ge\; b-a$，那么实际上是不可能存在合适的$GG$能满足最短路是$d[i]d[i]$的，直接判为No，否则就可以连这两条边。
那么是不是对所有这样的点都连两条边呢？实际上考虑第一次连两条边的点是$yy$，那么一定满足$d[y]\equiv d[i](\mathrm{m}\mathrm{o}\mathrm{d}2)d[y]\backslash equiv\; d[i]\backslash pmod\; 2$，因此可以连接$ii$和$yy$，边权为${\displaystyle \frac{d[i]-d[y]}{2}}\backslash dfrac\{d[i]-d[y]\}\{2\}$，这样就只需要连一条边了。
时间复杂度$O(\min (n^2,m)\log n)O(\backslash min(n^2,m)\backslash log\; n)$。

vector<pair<int, int> >a;
int d[N];
map<pair<int, int>, bool>mp;

int main() {
    int n = fast_IO::read(), m = fast_IO::read();
    for (int i = 1; i <= n; ++i) {
        d[i] = fast_IO::read();
        a.push_back(make_pair(d[i], i));
    }
    int minn = INF;
    for (int i = 1; i <= n; ++i)minn = min(minn, d[i]);
    if (d[1] != d[n] || d[1] != minn) {
        puts("No");
        return 0;
    }
    sort(a.begin(), a.end());
    vector<tuple<int, int, int> >ans;
    int last = 0;
    for (auto [dist, y] : a) {
        if (y == 1)continue;
        if (y == n) {
            ans.push_back(make_tuple(1, n, d[n]));
            mp[make_pair(1, n)] = true;
        }
        else if ((dist & 1) == (d[n] & 1)) {
            ans.push_back(make_tuple(1, y, dist - d[n] >> 1));
            mp[make_pair(1, y)] = true;
        }
        else {
            if (!last) {
                int a = dist / 2;
                int b = (dist + 1) / 2;
                if (a + d[n] >= b) {
                    ans.push_back(make_tuple(1, y, a));
                    ans.push_back(make_tuple(y, n, b));
                    mp[make_pair(1, y)] = true;
                    mp[make_pair(y, n)] = true;
                }
                else {
                    puts("No");
                    return 0;
                }
            }
            else {
                if (last < y) {
                    ans.push_back(make_tuple(last, y, dist - d[last] >> 1));
                    mp[make_pair(last, y)] = true;
                }
                else {
                    ans.push_back(make_tuple(y, last, dist - d[last] >> 1));
                    mp[make_pair(y, last)] = true;
                }
            }
            last = y;
        }
    }
    if (m < ans.size()) {
        puts("No");
        return 0;
    }
    m -= ans.size();
    int nowx = 1, nowy = 2;
    while (m && nowx <= n) {
        if (!mp.count(make_pair(nowx, nowy))) {
            ans.push_back(make_tuple(nowx, nowy, 1000000000));
            --m;
        }
        ++nowy;
        if (nowy > n)++nowx, nowy = nowx + 1;
    }
    if (m) {
        puts("No");
        return 0;
    }
    puts("Yes");
    for (auto [x, y, z] : ans)
        printf("%d %d %d\n", x, y, z);
    return 0;
}