#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
const int Nmax=105,oo=(1<<30);
int n,m,D[Nmax];
vector<pair<int,int>>G[Nmax];
struct compara
{
  bool operator()(int i,int j)
  {
      return D[i]>D[j];
  }
};
priority_queue<int,vector<int>,compara>Q;
bool incoada[Nmax];
void citire()
{int i,k,j,c;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>k>>j>>c;
        G[k].push_back(make_pair(j,c));
    }
}
void dijkastra(int p)
{int i;
for(i=1;i<=n;i++)
    D[i]=oo;
D[p]=0;
Q.push(p);
incoada[p]=true;
while(!Q.empty())
{
    int x=Q.top();
    Q.pop();
    incoada[x]=false;
    for(size_t i=0;i<G[x].size();i++)
    {
        int Vecin=G[x][i].first;
        int Cost=G[x][i].second;
        if(D[x]+Cost<D[Vecin])
        {
            D[Vecin]=D[x]+Cost;
            if(!incoada[Vecin])
            {
                Q.push(Vecin);
                incoada[Vecin]=true;
            }
        }
    }
}
}
void afisare()
{int i;
    for(i=2;i<=n;i++)
    {
        if(D[i]!=oo)
            cout<<D[i]<<' ';
        else
            cout<<"-1"<<' ';
    }

}
int main()
{
    citire();
    dijkastra(1);
    afisare();
    return 0;
}