#include <bits/stdc++.h>
#define oo 1e9

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct Graf
{
    int nod , cost;
    bool operator < (const Graf & e) const
    {
        return cost > e . cost;
    }
};

int n,m;
int dist[50005];
bitset<50005>viz;
vector<pair<int,int> >L[50005];
priority_queue<Graf>q;
Graf p;

void Initializare()
{
    int i;
    for(i=2;i<=n;i++)
        dist[i]=oo;
}

int main()
{
    int x,y,cost;

    fin>>n>>m;

    while(m--)
    {
        fin>>x>>y>>cost;
        L[x].push_back({y,cost});
    }

    Initializare();
    q.push({1,0});
    while(!q.empty())
    {
        p=q.top();
        q.pop();

        if(!viz[p.nod])
        {
            viz[p.nod]=1;

            for(auto i:L[p.nod])
                if(dist[i.first]>dist[p.nod]+i.second)
                {
                    dist[i.first]=dist[p.nod]+i.second;
                    q.push({i.first,dist[i.first]});
                }
        }
    }

    for(int i=2;i<=n;i++)
        if(dist[i]==oo)fout<<0<<" ";
        else fout<<dist[i]<<" ";

    fin.close();
    fout.close();
    return 0;
}