#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
#define inf 0x3f3f3f3f
using namespace std;
vector <pair<int,int> >g[50005];
int n,m,d[50005];
bool viz[50005];
queue <int> q;

void dijkstra()
{
    int k;
    q.push(1);
    d[1]=0;
    viz[1]=1;
    while(!q.empty())
    {
        k=q.front();
        vector <pair<int,int> >::iterator i;
        viz[k]=0;
        q.pop();
        for(i=g[k].begin();i!=g[k].end();++i)
        {
            if(d[i->first]>d[k]+i->second)
            {
                d[i->first]=d[k]+i->second;
                if(viz[i->first]==0)
                {
                    viz[i->first]=1;
                    q.push(i->first);
                }
            }
        }
    }
}
int main()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    int a,b,c,i,j;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        g[a].push_back(make_pair(b,c));
    }
    memset(d,inf,sizeof(d));
    dijkstra();
    for(i=2;i<=n;i++)
    {
        if(d[i]!=inf)
            fout<<d[i]<<" ";
        else fout<<0<<" ";
    }
    return 0;
}