    #include <bits/stdc++.h>
    using namespace std;
    #include <math.h>
    #include <iomanip>
    #include <cstdint>
    #include <string>
    #include <sstream>
    template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
    template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
    #define rep(i,n) for (int i = 0; i < (n); ++i)
    typedef long long ll;
    using P=pair<ll,ll>;
    const int INF=1001001001;
    const int mod=1e9+7;
    
    struct edge{
      int to;
      ll w;
      edge(int to,ll w):to(to),w(w){}
    };
    using Graph=vector<vector<edge>>;
    
    int n,m;
    
    auto dijkstra(int s,Graph G){
      vector<ll>dist(n,INF);
      dist[s]=0;
      priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>q;
      q.push({dist[s],s});
      while(!q.empty()){
        int v=q.top().second;
        ll d=q.top().first;
        q.pop();
        if(d>dist[v]){continue;}
        for(auto e:G[v]){
          if(chmin(dist[e.to],dist[v]+e.w)){
            q.push({dist[e.to],e.to});
          }
        }
      }
      return dist;
    }

    
    void solve(){
      Graph G(2005);
      cin>>n>>m;
      vector<int>p(n,INF);
      rep(i,m){
        int a,b,c;
        cin>>a>>b>>c;
        a--;b--;
        G[a].push_back(edge(b,c));
        if(a==b){
          chmin(p[a],c);
        }
      }
      vector<vector<ll>>t;
      rep(i,n){
        auto r=dijkstra(i,G);
        t.push_back(r);
      }
      rep(i,n){
        int mn=INF;
        rep(j,n){
          if(i==j){continue;}
          int res=t[i][j]+t[j][i];
          chmin(mn,res);
        }
        if(mn==INF&&p[i]==INF){cout<<-1<<endl;}
        else{cout<<min(p[i],mn)<<endl;}
      }
    }
    int main(){
      solve();
      return 0;
    }

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dbl;
#define REP(i, n) for (ll i = 0; i < ll(n); ++i)
#define REPD(i, n) for (ll i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = a; i <= ll(b); i++)
#define FORD(i, a, b) for (ll i = a; i >= ll(b); i--)
#define FORA(i, I) for (const auto &i : I)
#define ALL(x) x.begin(), x.end()
#define SIZE(x) ll(x.size())
const ll INF = 1LL << 60;
const ll MOD = 1'000'000'007LL;
const dbl EPS = 1e-12;
const dbl PI = 3.14159265358979323846;
#define coutALL(x)                                \
    for (auto i = x.begin(); i != --x.end(); ++i) \
        cout << *i << ' ';                        \
    cout << *--x.end() << endl;
ll myceil(ll a, ll b)
{
    return (a + (b - 1)) / b;
}
ll myfloor(ll a, ll b) { return a / b; }
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}

using Graph = vector<vector<int>>;

vector<bool> seen;
vector<int> colors;
bool valid(const Graph &G, int v, int color)
{
    for (auto nx : G[v])
    {
        if (colors[nx] == color)
            return 0;
    }
    return 1;
}
void dfs(const Graph &G, int v, vector<int> &nodes)
{
    if (seen[v])
        return;
    nodes.push_back(v);
    seen[v] = true;
    for (auto next : G[v])
    {
        dfs(G, next, nodes);
    }
}
void colornize(const Graph &G, const vector<int> &nodes, int idx, ll &num)
{
    if (idx == nodes.size())
    {
        num++;
        return;
    }
    for (int color = 1; color <= 3; ++color)
    {
        if (valid(G, nodes[idx], color))
        {
            colors[nodes[idx]] = color;
            colornize(G, nodes, idx + 1, num);
            colors[nodes[idx]] = 0;
        }
    }
}

void solve()
{
    int N, M;
    cin >> N >> M;
    Graph G(N);
    REP(i, M)
    {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    seen.assign(N, false);
    colors.assign(N, 0);
    vector<int> nodes;
    ll ans = 1;
    REP(start, N)
    {
        if (seen[start])
            continue;
        nodes.clear();
        dfs(G, start, nodes);
        ll tmp = 0;
        colornize(G, nodes, 0, tmp);
        ans *= tmp;
    }
    cout << ans << endl;
}
signed main()
{
    cout << fixed << setprecision(15);
    solve();
    return 0;
}