题意简述：

给定一些有向边，对她们赋上边权 $w\in[1,9]$，使得每条 $1\to n$ 的简单路径长相等。

---

不得不说这题相当有趣，，

比赛的时候写的是钦定每条在 $1\to n$ 路径上边权为 $1$，统计路径总数以及每条路径的长度和，然后求出公共 gcd 和 lcm，通分后再进行一遍约分。但是很遗憾的是，在钦定边权为 $1$ 时就可能出现 out of range of [1,9] 的情况。每条边的边权无法确认，于是我们只能从题目本身入手

然后就可以发现，，，由于给定的边权 $w\in[1,9]$，又有 $dis_u + w(u,v) = dis_v$，说明 $dis_v - dis_u\in[1,9]$。仔细想想这不就可以建差分约束系统求解了吗？

---

简单介绍一下差分约束，单源最短路中我们有：

$$dis_{to}\le dis_u + w(u,to)$$

故有：

$$dis_{to} - dis_u\le w(u, to)$$

也就是说，如果给定 $x + y \ge z$，就可以转化成 $z - y\le x$，然后 add(y, z, x) $y\to z$ 建边。

在这道题中我们有 $a\to b$ 的边，同时有：

$$1\le dis_b - dis_a \color{orange}\Rightarrow \color{c}dis_a - dis_b \le -1$$

$$dis_b - dis_a\le 9$$

所以建边：add(b, a, -1), add(a, b, 9)

最后 SPFA 判断差分约束系统是否有解（是否有负环），没了。

没了？没了。

当然还有一些注意事项：

• 题目给的是有向边，要判断是否能从 $1\to n$

• 不在 $1\to n$ 路径上的边的边权可以随便标，不会对答案产生影响，所以我们先标记出 $1\to n$ 路上的点，然后再建边。对那些“无用”边建边会让我们得到错误的约束。

---

$\texttt{Code:}$

const int MAXN = 1e3 + 3;
const int MAXM = 2e3 + 3;
const int LEN = 1 << 11;

inline int read() {
    int x = 0; bool f = 1; register char c = getchar();
    for(; !std::isdigit(c); c = getchar()) f ^= c == '-';
    for(; std::isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? x : -x;
}

int n, m, u[MAXM], v[MAXM], dis[MAXN], times[MAXN]; 
bool inq[MAXN], vis1[MAXN], visn[MAXN];

int fa[MAXN];

inline int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
inline void merge(int x, int y) {
    int a = find(x), b = find(y);
    if(a == b) return ;
    fa[a] = b;
}

struct Edges {
    int to, dis, nxt;
    Edges() {}
    Edges(int to, int dis, int nxt): to(to), dis(dis), nxt(nxt) {}
} edge[MAXM << 1];

int head[MAXN];

inline void addEdge(int u, int v, int d) {
    static int cnt = 0;
    edge[++cnt] = Edges(v, d, head[u]);
    head[u] = cnt;
}

std::vector<int> G[MAXN], nG[MAXN];
inline void addEdge(int u, int v, std::vector<int> ver[]) {
    ver[u].push_back(v);
}

void dfs(int x) {
    int size = G[x].size();
    for(int i = 0; i < size; ++i) {
        int to = G[x][i];
        if(vis1[to]) continue;

        vis1[to] = 1; dfs(to);
    }
}
void nDfs(int x) {
    int size = nG[x].size();
    for(int i = 0; i < size; ++i) {
        int to = nG[x][i];
        if(visn[to]) continue;

        visn[to] = 1; nDfs(to);
    }
}

struct Queue {
    int l, r, q[LEN + 10];
    Queue(): l(1), r(0) {}

    inline void push(int x) { q[++r & (LEN - 1)] = x; }
    inline void pop() { ++l; }
    inline int front() { return q[l & (LEN - 1)]; }
    inline bool empty() { return l > r; }
};

inline bool SPFA(int s) {
    std::memset(dis, 0x3f, sizeof dis);
    dis[s] = 0; inq[s] = 1; times[s] = 1;
    Queue q; q.push(s);

    while(!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = 0;
        for(int i = head[u]; i; i = edge[i].nxt) {
            int v = edge[i].to;
            if(dis[u] + edge[i].dis < dis[v]) {
                dis[v] = dis[u] + edge[i].dis;
                if(++times[v] > n) return 0;
                if(!inq[v]) q.push(v), inq[v] = 1;
            }
        }
    }
    return 1;
}

signed main() {
    n = read(), m = read();

    for(int i = 1; i <= n; ++i) fa[i] = i;

    for(int i = 1; i <= m; ++i) {
        u[i] = read(), v[i] = read();
        addEdge(u[i], v[i], G), addEdge(v[i], u[i], nG);
        merge(u[i], v[i]);
    }

    if(find(1) != find(n)) {
        puts("-1");
        return 0;
    }

    dfs(1); nDfs(n);

    static bool flag[MAXN] = {0};
    for(int i = 1; i <= n; ++i) if(vis1[i] && visn[i]) flag[i] = 1;
    if(!vis1[n]) {
        puts("-1");
        return 0;   
    }
    flag[1] = flag[n] = 1;

    for(int i = 1; i <= m; ++i)
        if(flag[u[i]] && flag[v[i]]) addEdge(u[i], v[i], 9), addEdge(v[i], u[i], -1);

    if(!SPFA(1)) {
        puts("-1");
        return 0;
    }

    printf("%d %d\n", n, m);
    for(int i = 1; i <= m; ++i) {
        printf("%d %d ", u[i], v[i]);
        if(flag[u[i]] && flag[v[i]]) printf("%d\n", dis[v[i]] - dis[u[i]]);
        else puts("1");
    }
    return 0;
}

为了能让大家有自己的思考与理解，题解代码中没有注释。详细注释版本的放在剪贴板中。

另：博主是个菜鸡，如果哪里有误麻烦指出orz