#include <fstream>
#include <vector>
#include <set>
#define inf 1e9
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector <pair<int,int>> v[50005];
int d[50005],f[50005],N,M;
set<pair<int,int>>S;
pair<int,int> a;
void Relaxare(int nod)
{
    int i,mn=inf,p=0;
    S.erase(make_pair(d[nod],nod));
    for(i=0; i<v[nod].size(); i++)
        if(d[v[nod][i].first]>v[nod][i].second+d[nod])
        {   S.erase(make_pair(d[v[nod][i].first],v[nod][i].first));
            d[v[nod][i].first]=v[nod][i].second+d[nod];
            S.insert(make_pair(d[v[nod][i].first],v[nod][i].first));
        }
    if(!S.empty())
        Relaxare((*S.begin()).second);
}
int main()
{
    int i,x,y,z;
    fin>>N>>M;
    for(i=1; i<=M; i++)
    {
        fin>>x>>y>>z;
        a.first=y;
        a.second=z;
        v[x].push_back(a);
    }
    d[1]=0;
    for(i=2; i<=N; i++)
    {
        d[i]=inf;
    }
    Relaxare(1);
    for(i=2; i<=N; i++)
    {
        if(d[i]!=inf)
            fout<<d[i]<<" ";
        else
            fout<<"0 ";
    }
}