AOJ 1169 最強の呪文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1169&lang=jp
　若干消化不良なのであてにならないかもしれませんが……。
　有向グラフが与えられ、その辺の重みは英単語で表されます。ゴールまで行くとき、通った辺の単語をつなげてできる単語が辞書順最小になる行き方を求め、その単語を出力しろ。ただし辞書順最小を更新する負閉路があるときは-1を出力しろ。
　というのが問題概要。
　一見普通のダイクストラでできそうに見えます。
　ところで、ダイクストラ法はa → bが最短経路であるとき、cost(a, b) + cost(b, c) は cへの最短経路の候補になる、というのを繰り返す操作でした。
　なのでこの問題の場合はそのまま適応できません。a → bへのルートがa, aaの二通りあり、b → cがcであるとき、a → b　の最短はaですが、b → c　の最短はa+cではなくaacになります。このように、この問題の場合はその後のルートに依存してある二点間の最適なルートが決まるので、ゴール地点から逆順に回して単語を構築していけばいいことになります。
　ここまではまあいいのですが、やっかいなのが負閉路の検出です。ベルマンフォード法で普通に負閉路検出するとすべての負閉路を検出してしまいますが、この問題の場合「辞書順最小を更新しない負閉路」というものがあるので非常にやっかいです。正直よくわからなかったので、適当な回数まわして、ベルマンフォード法の緩和操作がスタート地点までの最適経路に及ぶようならダメ、としました。もっとスマートな方法があると思うんですが、負閉路があるときの緩和操作の流れがよくわからないし、うまい方法は思いつきませんでした……。

struct Edge {
    int from, to; string spell;
    Edge(int f, int t, string s)
         :from(f), to(t), spell(s){}
};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, A, S, G;
    while(cin >> N >> A >> S >> G && N){
        vector<Edge> es;
        int x_, y_; string s;
        rep(i, A){
            cin >> x_ >> y_ >> s;
            es.push_back(Edge(y_, x_, s));
        }
        vector<string> dist(N, "~"); dist[G] = "";
        bool fail = false;
        rep(repnum, N * 6){
            bool update = false, update_s = false;
            for(const Edge& e : es)
              if(dist[e.from] != "~" && dist[e.to] > e.spell + dist[e.from]){
                  dist[e.to] = e.spell + dist[e.from];
                  update = true;
                  if(e.to == S) update_s = true;
              }
            if(!update) break;
            if(repnum == N && dist[S] == "~") break;
            if(repnum > N && update_s){
                fail = true;
                break;
            }
        }
        if(dist[S] == "~" || fail) cout << "NO" << endl;
        else cout << dist[S] << endl;
    }
    return 0;
}