#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
int N,M;
int dist[50001];

vector<int> vec;
vector< pair<int,int> > A[50001];

void citeste(const char* nume)
{
  ifstream f(nume);
  f>>N;
  f>>M;
  int j,k,c;
  for(int i=1;i<=M;i++)
    {
        f>>j;
        f>>k;
        f>>c;
        A[j].push_back(make_pair(k,c));
    }
  f.close();
}

int dijkstra(int s,int v)
{
  dist[s]=0;
    for(int i=1;i<=N;i++)
    {
      if(i!=s)
       dist[i]=(1<<30);
      vec.push_back(i);
    }

    while(!vec.empty())
    {
        int u;
        int Min=(1<<30);
        for(int i=0;i<vec.size();i++)
            if(dist[vec[i]]<Min)
            {
                Min=dist[vec[i]];
                u=vec[i];
            }
        vec.erase(remove(vec.begin(), vec.end(), u), vec.end());
        for(int i=0;i<A[u].size();i++)
        {
            int t=A[u][i].first;
            if(t>0)
            {
                   int alt=dist[u] + A[u][i].second;
                   if(alt<dist[t])
                   {
                     dist[t]=alt;
                   }
            }
            else
             break;
        }

    }

   return dist[v];
}

int main()
{
    citeste("dijkstra.in");
    ofstream f("dijkstra.out");
    for(int i=2;i<=N;i++)
    {
       int val=dijkstra(1,i);
       if(val == (1<<30))
         f<<0<<" ";
       else
        f<<val<<" ";

    }
    f.close();
    return 0;
}