#include<fstream>
#include<algorithm>
#include<bitset>
#include<queue>
using namespace std;

struct coord
{
    int cost,nod;
};

struct coada
{
    int varf,relax;
    inline bool operator < (const coada& e) const
    {
        return relax > e.relax;
    }
};

vector <coord> v[50002];
int n,m,d[50002];
const int oo=1<<30;
int main()
{
    register int i,x;
    coord y;
    ifstream fin("dijkstra.in");
    fin>>n>>m;
    for (i=1;i<=m;i++)
        {
            fin>>x>>y.nod>>y.cost;
            v[x].push_back(y);
        }
    priority_queue< coada >q;
    register int costarico;
    register coada kl;
    d[1]=0;
    for (i=2;i<=n;i++)
        d[i]=oo;
    x=1;
    kl.varf=1;
    kl.relax=0;
    q.push(kl);
    bitset < 50002 > viz;
    register int cnt = 0;
    while (!q.empty() && cnt!=n){
            x=q.top().varf;
            costarico=q.top().relax;
            q.pop();
            if (costarico==d[x])
            {
                ++cnt;
                viz[x] = 1;
                for(vector < coord > :: iterator it = v[x].begin(); it!=v[x].end(); ++it){
                    register int node = (*it).nod;
                    if (!viz[node] && d[node]>d[x]+(*it).cost)
                    {
                        d[node]=d[x]+(*it).cost;
                        kl.varf = (*it).nod;
                        kl.relax = d[node];
                        q.push(kl);
                    }
                }
            }
        }
    ofstream fout("dijkstra.out");
    for (register int i = 2;i<=n;++i)
        if (d[i]!=oo)
            fout<<d[i]<<" ";
        else fout<<"0 ";
    fout<<"\n";
    return 0;
}