この問題はトポロジカルソート、グラフ上のDP、二分探索を問います。

最初に $K$ の最小値が存在するのかを調べます。

問題では街 $1$ から街 $N$ を通過するまでに雪玉の大きさを $0$ にすることを目標にしているのが見て取れます。
よって与えられたグラフ $G$ において街 $1$ から辺をたどって街 $N$ へ行く方法を調べることで、次の式が成り立つことが分かります。
ただし $n$ は街 $1$ 以外に通過した街の個数を表します。

• $W+\sigma(x_0,x_1,x_2,\dots ,x_n,x_{n+1})-nK\le 0$ ※

ただし $\sigma(x_0,x_1,x_2,\dots ,x_n)$ は街 $x_0,x_1,x_2,\dots ,x_n$ の順で通過したときの道の長さの総和を表します。
すなわち $i$ 番目の行動で街 $x_i$ を通過したとすると、$i=0,1,\dots ,n$ に対して街 $x_i,x_{i+1}$ をつなぐ道の長さ $\text{path}_{x_i,x_{i+1}}$ において、

• $\sigma(x_0,x_1,x_2,\dots ,x_n,x_{n+1})=\displaystyle\sum_{k=0}^{n} \text{path}_{x_k,x_{k+1}}$

と定義します。ただし $x_0=1,x_{n+1}=N$ としています。

上の不等式から $K\ge \cfrac{W+\sigma(x_0,x_1,x_2,\dots ,x_n,x_{n+1})}{n}$ ...☆ を得ることができます。ゆえに $K$ の最小値が存在することが分かります。※2

(ここでは $n\gt 0$ の場合のみ考えます)

$K$ の最小値が存在することは確認できましたが、$n,\sigma(x_1,x_2,\dots ,x_n,x_{n+1})$ は経由の仕方によって変化します。
ここで☆の式を見ると、次のことが明らかに見て取れます。

• $W+\sigma(x_0,x_1,x_2,\dots ,x_n,x_{n+1})$ が小さいほど、また $n$ が大きいほど $K$ の値が小さくなる...①
• $W+\sigma(x_0,x_1,x_2,\dots ,x_n,x_{n+1})$ が大きいほど、また $n$ が小さいほど $K$ の値が大きくなる...②

よって考え得るものはこの $2$ 通りに絞られます( $\sigma$ を最大化させるか、最小化させるか)。どちらで考えることが最適なのでしょうか？

実は、rate君が最適に移動する手段は②を満たす行動を取ることなのです。なぜかというと、rate君的には雪玉の大きさを維持したい思いが強いため、わざわざ重さを減らすような移動を選ぶことはしない方がよいためです。
逆にその移動をしてしまうと、rate君的には最短でたどりつけるように思えますが、$K$ を小さくするほど②を満たすような移動をした瞬間に突破されてしまう(適切な移動をすることで街 $N$ にたどり着けてしまう)のです。

したがって本問題は次のように言い換えることができます。

• 上の不等式(☆)を満たすような $K$ の最小値のうち、使用した道の長さの総和が最大になるように移動をしたときのものを求めよ。

もしこれが最小の問題なら、典型的な単一始点最短経路探索問題に他なりません。※2 今回は最大なのでこの問題をさらに言い換える必要があります。

解法1(嘘解法！)

少し観察してみると制約から $A_i\le 10^9$ と書かれているので、すべての道の長さに対し $10^9$ で引いたものに重みを置き換えたグラフを考えることが適切だと思われます。
(もちろん置き換えなくても解ける方法はありますが、ダイクストラ法の性質？から時間がより長くかかってしまうことが考えられます)

置き換えた後、その総和 ${\color{red}\min}\bigg(\displaystyle\sum_{k=0}^{n} \text{path}_{x_k,x_{k+1}}\bigg)$ から $n\times 10^9$ を引くことで道の長さの総和の最大値を計算することができます。
ただし街 $1$ から街 $N$ にたどり着く方法が存在しないなら答えは $1$ となります( $K$ は正整数であることに注意)。

しかし、この方法では ${\color{red}\min}\bigg(\displaystyle\sum_{k=0}^{n} \text{path}_{x_k,x_{k+1}}\bigg)-n\times 10^9$ が正整数に収まらないケースが存在します。
なのでその場合はこの方法で答えを求めることができません。

では、どうしたらよいでしょうか？

解法2

上の ☆ 式を見てみると、$\sigma(x_0,x_1,x_2,\dots ,x_n,x_{n+1}),n$ に依存することがわかります。ここで問題の制約である、同じ街を $2$ 度訪れることができないことから、greentea君が移動する街の順番の場合の数は有限であることがわかります。
また街 $1$ から移動してたどり着けない街は一度も訪れないので、訪れる街の順番の場合の数に起因しません(その街は訪れない、つまりその街を無いものとして考えればよいため)。ゆえに $n$ はただ一つに定まることがわかります。
したがって ☆ 式は $\sigma(x_0,x_1,x_2,\dots ,x_n,x_{n+1})$ にのみ依存することがわかります。

$\sigma(x_0,x_1,x_2,\dots ,x_n,x_{n+1})$ に依存するものは、どのような街の順番で訪れたかです。
しかし制約より同じ街を $2$ 度訪れることができないことから、街を訪れる順番が定まるといったことは、前にも書きました。つまり、与えられるグラフはDAG、すなわち有向非巡回グラフであることがわかります。
このことから、トポロジカルソートを用いて街 $1$ から移動する順番を決定することが可能であることが見て取れます。

こうしてグラフの探索の順番が定まりました。

突然ですがここで動的計画法、いわゆるDPについて考えてみましょう。
DPを適用できるような問題において、DPに対する遷移をグラフにして考えてみると、遷移した後の状態 $\text{S}$ が、$\text{S}$ になる前までに同じ状態になるような遷移方法が存在しないといった性質があります。
よって本問題でも、グラフがDAGであるのでDPを適用できることがわかります。

では早速DPの遷移を考えてみます。まず、

• $\text{dp}[v]:=$ 街 $1$ から街 $v$ にたどり着くとき、greentea君が移動毎に保てる雪玉の大きさの最大値

と定義すると、初期状態として $\text{dp}[1]=W,\text{dp}[v]=-\infty\ (2\le v\le N)$ とします。

そしてdpの遷移は、街 $v$ から $1$ 回移動することでたどり着ける街を $u_1,u_2,\dots,u_m$ とすると

• $\text{dp}[u]\le 0$ の場合、$\text{dp}[u]=\text{dp}[u]$ (何も変更を加えない)
• $\text{dp}[u]\gt 0$ の場合、$\text{dp}[u]=\max(\text{dp}[u],\text{dp}[v]+\text{path}_{v,u}-K)$

となり、最終的な答えは $\text{dp}[N]$ ですが、これをそのまま答えるわけではありません。

この遷移式では $K$ に依存しますが、肝心の $K$ が定められていません。ここで、先ほどの $K$ が $\sigma(x_0,x_1,x_2,\dots ,x_n,x_{n+1})$ にのみ依存することを考えてみます。
$\sigma(x_0,x_1,x_2,\dots ,x_n,x_{n+1})$ が大きくなれば $K$ が大きく、小さくなれば $K$ が小さくなるといった単調性を持つことがわかります。よって $K$ は二分探索を用いて探索することが可能です。

以上から、$K$ を二分探索する際の評価関数としてグラフ上のDPを用いて、「条件」を満たす最小の $K$ を求めることができることがわかりました。
またここでの「条件」とは、greentea君が街 $N$ に訪れるときに雪玉の大きさが $0$ 以下であることであるので、DPの時の最終的な答えは $\text{dp}[N]\le 0$ を満たしているかどうかで決まります。

グラフ上のDPは、例えばDFSなどのグラフ探索アルゴリズムを用いて実装すればよいです(言わずもがな、DAGのために順番は定まるため)。
ゆえに $O(N\log_{}{N}+N\log_{}{A})$ でこの問題を解くことができます。ただし $A=10^{17}$ です。※3

※途中で経由する街、すなわち街 $1,N$ を除く通過する街に到達するときに、greentea君の雪玉の大きさを $0$ 以下にする必要がないということを前提に立式しています。すなわちこの式を満たしていたとしても途中で経由する街で雪玉の大きさを $0$ 以下になることがあり得ることに注意してください。

※2 街 $N$ に到達するときは $n\gt 0$ となるので必ず存在することがわかります(到達できないときは $K$ を求めることなく答えが $1$ になります)。

※3 $\sigma(x_0,x_1,x_2,\dots ,x_n,x_{n+1})$ は制約から、取りうる最大値が $10^{17}$ であるためです。