#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x) & (-x))
using namespace std;
const ll inf = 1e18;
const ll mod = 1e9 + 7;

struct E {
    ll to, len, id;
};
vector<E> G[105];

struct Node {
    ll id, val;
    bool operator<(const Node &rhs) const {
        return val > rhs.val; // 小根堆
    }
};

void solve() {
    ll n, m;
    cin >> n >> m;

    vector<array<ll, 4>> edge;

    for (ll i = 1; i <= m; i++) {
        ll x, y, d;
        cin >> x >> y >> d;

        edge.push_back({x, y, d, i});
        G[x].push_back({y, d, i});
        G[y].push_back({x, d, i});
    }

    ll ans = inf;
    for (ll i = 1; i <= m; i++) {
        priority_queue<Node> q;

        auto [x, y, road, miss] = edge[i - 1];

        ll dis[105];
        fill(dis, dis + 105, inf);

        q.push({x, 0});
        dis[x]=0;

        while (q.size()) {
            ll now = q.top().id, val = q.top().val;
            q.pop();

            if (dis[now] < val) continue;

            for (auto next : G[now]) {
                auto [to, len, id] = next;
                if (id == miss) continue;

                if (dis[to] > dis[now] + len) {
                    dis[to] = dis[now] + len;
                    q.push({to, dis[to]});
                }
            }
        }
        ans = min(ans, dis[y]+road);
    }

    if(ans<=1e7)cout << ans << '\n';
    else cout<<"No solution.";
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TT=1;
    //cin>>TT;
    while(TT--) solve();
    return 0;
}