Problem: problem

AOR Ika likes rooted trees with a fractal (self-similar) structure. Consider using the weighted rooted tree $ T $ consisting of $ N $ vertices to represent the rooted tree $ T'$ with the following fractal structure.

* $ T'$ is the addition of a tree rooted at $ x $ and having a tree structure similar to $ T $ (same cost) for each vertex $ x $ of $ T $.
* The root of $ T'$ is the same as that of $ T $.



The tree represented in this way is, for example, as shown in the figure below.

<image>

AOR Ika is trying to do a depth-first search for $ T'$, but finds that it takes a lot of time to trace all the vertices. Therefore, we decided to skip some node visits by performing a depth-first search with a policy of transitioning with a probability of $ p $ and not transitioning with a probability of $ 1-p $ at the time of transition during a depth-first search. Given $ T $ and the probability $ p $, find the expected value of the sum of the costs of all edges to follow when performing a depth-first search for $ T'$. The information of $ T $ is given by the number of vertices $ N $ and the information of the edges of $ N-1 $, and the vertex $ 1 $ is the root. Each vertex is labeled $ 1,2, \ dots, N $, and the $ i \ (1 \ le i \ le N-1) $ th edge costs the vertices $ x_i $ and $ y_i $ $ c_i $ It is tied with. The non-deterministic algorithm of the depth-first search that transitions to a child with a probability of $ p $, which is dealt with in this problem, is expressed as follows. The sum of the costs of the edges that the output $ \ mathrm {answer} $ follows.

1. Prepare an empty stack $ S $.
2. Set $ ​​\ mathrm {answer} = 0 $
3. Push the root vertex of $ T'$ to $ S $.
4. Extract the first element of $ S $ and make it $ x $.
5. For each child $ c $ of $ x $, do the following with probability $ p $ and do nothing with probability $ 1-p $.
* Add vertex $ c $ to $ S $. Then add the weight of the edge connecting $ x $ to $ c $ to $ \ mathrm {answer} $.
6. If S is not empty, transition to 3.
7. Output $ \ mathrm {answer} $.



output

Print the answer in one line. If the relative or absolute error is less than $ 10 ^ {-6} $, then AC. Also, output a line break at the end.

Example

Input

0.75
4
1 2 1
2 3 3
3 4 10


Output

24.8569335938

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using vl=vector<long long>;
using pii=pair<int,int>;
using pll=pair<long long,long long>;
#define ITR(i,c) for(auto i=begin(c);i!=end(c);++i)
#define FORE(x,c) for(auto &x:c)
#define FOR(i,a,n) for(int i=a,i##_len=(int)(n);i<i##_len;++i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for(int i=(int)(n);i>=0;--i)
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)   // c++14
#define SZ(c) ((int)c.size())
#define EXIST(c,x) (c.find(x)!=end(c))
#define dump(...)
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
#define INF (1001001001)
#define INFLL (1001001001001001001ll)
template<class T> ostream& operator << (ostream &os,const vector<T> &v) {
    ITR(i,v) os << *i << (i==end(v)-1 ? "" : " "); return os; }
template<class T> istream& operator >> (istream &is,vector<T> &v) {
    ITR(i,v) is >> * i; return is; }
template<class T> istream& operator >> (istream &is, pair<T,T> &p) {
        is >> p.first >> p.second; return is; }
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
//------------------------------------------------------------------------------
struct before_main_function {
    before_main_function() {
        #ifdef int
            #undef INF
            #define INF INFLL
            #define stoi stoll
        #endif
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
    }
} before_main_function;
//------------------------------------------------------------------------------

struct node {
    int parent;
    double p;
    vector<pii> c;
};
double P;
int N;
double ex;
vector<node> T;
vector<vector<pii>> U;
void make_tree(int i=0) {
    REP(j,SZ(U[i])) {
        pii e=U[i][j];
        if(e.first==T[i].parent) continue;
        T[i].c.push_back(e);
        T[e.first].p=T[i].p*P;
        T[e.first].parent=i;
        make_tree(e.first);
    }
}
double dfs(int i=0) {
    if(SZ(T[i].c)==0) return 0;
    double ret=0;
    FORE(x,T[i].c) {
        ret+=x.second*T[x.first].p+dfs(x.first);
    }
    return ret;
}
double dfs2(int i=0) {
    if(SZ(T[i].c)==0) return T[i].p * ex;
    double ret=0;
    FORE(x,T[i].c) {
        ret+=x.second * T[x.first].p + dfs2(x.first);
    }
    return ret + T[i].p * ex;
}
signed main() {
    cin>>P>>N;
    T=vector<node>(N);
    U=vector<vector<pii>>(N);
    REP(i,N-1) {
        int a,b,c;
        cin>>a>>b>>c;
        a--,b--;
        U[a].push_back({b,c});
        U[b].push_back({a,c});
    }
    T[0].parent=-1;
    T[0].p=1;
    make_tree();  // T????§????
    ex=dfs();
    cout<<dfs2()<<endl;
    return 0;
}