using namespace std;
#include <cstdio>
#include <vector>
#include <fstream>
#define maxn 256
#define oo 0x3f3f3f3f
#define pb push_back
#include <queue>
int n;

struct nod { int x, c; nod(){}; nod(int a, int b){x=a; c=b;};};
vector<nod> a[maxn];

int d[maxn];

inline int min(int a, int b)
{
  if(a<b) return a;
  return b;
}

struct cmp{
  bool operator()(const int &a, const int  &b)const 
  {
    if(d[a]>d[b])return 1;
    return 0;
  }
};


void solve()
{

  priority_queue<int, vector<int>, cmp> Q;
  
  memset(d, oo, sizeof(d));
  d[1]=0;

  Q.push(1);
  int u;
  vector<nod>::iterator it;
  while(!Q.empty())
    {
      u=Q.top();
      Q.pop();
      for(it=a[u].begin();it!=a[u].end();++it)
	if(d[it->x]>d[u]+it->c)
	  {
	    d[it->x]=d[u]+it->c;
	    Q.push(it->x);
	  }
    }

  int i;
  // for(i=1;i<=n;++i) printf("%d ", d[i]);

  freopen("tunel.out","w",stdout);
  printf("%d\n", d[n]*d[n]);


}


int main()
{
  ifstream f("tunel.in");
  f>>n;
  int m, p, q, c;
  f>>m;
  while(m--)
    {
      f>>p>>q>>c;
      a[p].pb(nod(q, c));
      a[q].pb(nod(p, c));
    }

  solve();
  return 0;
}