其实这题跑个dfs就好了，蒟蒻的我看大佬们好多都是期望dp什么的，感觉自己还不会来着

先要明白一个事情，假设你在第一个点的出边数是 k1 ,继续往下走，走到第 2 个点，它的出边数是 k2 ，就这样一直往下走，那么一直走到第 n 个点，那么从第一个点到第 n 个点的概率，就是 1 / (k1 * k2 * …… kn-1)

由全概率公式，我们可以知道，最后由起始点 1 到终点 n 路径长度的期望，实际上就等于每一种（由 1 到达 n 的事件的概率 * 这个事件走过的路径长度）的和

所以我们跑一个dfs，维护当前路径长度len以及k的累乘，抵达终点的时候将这一种可能对应的情况累加入答案即可

详见代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << '\n';
// #define int long long
#define ctz __builtin_ctzll         // 返回二进制表示中末尾连续0的个数
#define clz __builtin_clzll         // 返回二进驻表示中先导0的个数
#define count1 __builtin_popcountll // 返回二进制表示中1的个数
// 上面仨不是ll的时候记得调整
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 1e6 + 10000;
const double EPS = 1e-8;
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
ll dirr[8][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};

void LiangBaiKai()
{

}

void Aiden()
{
    ll m, n, k, sum = 0, ans = 0, num = 0, mi = INF, ma = -INF, x, y, z, len, t, l, r, cur, cnt = 0;
    string s1, s2;
    cin >> n >> m;
    long double anss = 0.0;
    vector g(n + 1, vector<pll>()); // 邻接表建图
    for (ll i = 1; i <= m;i++)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c}); // 有向图
    } 
    auto dfs = [&](auto dfs, ll x, ll k, ll len) -> void // x表示当前结点，k表示到达当前点的路径上各节点的出边数的累乘，len表示到达当前点经过的路径长度
    {
        if (x == n)
        {
            anss += 1.0 / k * len; // 抵达终点时，记录这一种情况对答案的贡献
            return;
        }
        for (auto [e, v] : g[x]) // 遍历子节点
            dfs(dfs, e, k * g[x].size(), len + v); // g[x].size就是当前点的出边个数
    };
    dfs(dfs, 1, 1, 0); // dfs初始化
    cout << fixed << setprecision(2) << anss << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    LiangBaiKai();
    int _ = 1;
    //cin >> _;
    while (_--)
        Aiden();
    return 0;
}

/*
                                                @@@@@@
                                                @@@@@@@@@@
                                                @@@@@@@@@@@@@
                                               @@@@@@@@@@@@@@@
                                               @@@@@@@@@@@
                                              @@@@
                                              @
                                  @@@@@@@@@@ @@ @@@@@@@@@@@@
                              @@@@@          @              @@@@@
                          @@@                @                   @@@
                       @@@                  @@                      @@@
                     @@                                                @@@
                   @@                                                     @@
                 @@                                                        @@
                @@                                                           @@
               @                                                              @@
              @          @@@@@@@@                                              @@
             @     @@@  @@@@@@@@@                                               @
            @@  @@@@@@@ @@@@@@@@  @@@@@@                                         @
            @  @@@@@@@@@@@@@@@@@@@@@@@@@@                                        @@
            @ @@@@@@@@@@@      @@@@@@@@@@@                                        @
             @@@@@@@@@@@@@   @@@@@@@@@@@@@@  @                             @@@@@@ @
            @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@    @@      @@@@@@         @@@        @
           @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@      @@@         @@@  @@@          @
          @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                                  @@@@@
         @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@     @@@
        @@@@@@       @@@@@@@@@@  @@@@@@@@@@@@@@                                        @@
       @@@@@  @@@@@@@ @@@@@@   @@   @@@@@@@@@@@                                     @@@
       @@@@@ @@@@@@@@  @@@@  @@@@@@@ @@@@@@@@@@@                                 @@
      @@@@@@  @@@@@@@ @@@@@  @@@@@@@  @@@@@@@@@@@@                            @@@@@@@
      @@@@@@@    @   @@@@@@  @@@@@@@ @@@@@@@@@@@@@@@@                      @@@@@@@@@@@
      @@@@@@@@@@@@@@@@@@@@@@@   @   @@@@@@@@@@@@@@@@@@@                @@@@@@@@@@@@@@@@@
      @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@          @@@@@@@@@@@@@@@@@@@@@
      @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@   @@@@@@@@@@@@@ @@@@@@@@@@
       @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@              @@@@@@@@@@
       @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@               @       @   @  @@@@@@@@@@@@
       @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@        @ @@@@@ @        @@@@   @   @@@@@@@@@@
        @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@    @@      @@      @@    @@@   @@@@@   @@@@@@@@@@
         @@@@@@@        @@@@@@@@@@@@@@         @@@@@@         @@@@@              @ @@@@@@@@
          @@@@@@        @@@@@@@@@@@                                             @  @@@@@@@@
           @@@@         @@@@@@@@                                              @@  @@@@@@@
              @@                                                              @@    @@@@@
               @@@                                                          @@
                  @@@                                                    @@@
                     @@@@@@@@@@@@                            @@@@@@@@@@@
                                @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
*/