#include<fstream>
#include<algorithm>
#include<bitset>
#include<queue>
#define Lim 1000000
using namespace std;
ifstream f("dijkstra.in");
struct coord
{
    int cost,nod;
};

struct coada
{
    int varf,relax;
    inline bool operator < (const coada& e) const
    {
        return relax > e.relax;
    }
};
int pos;
char Buffer[Lim];
inline void Read(int &x)
{
    while(Buffer[pos]<'0' || '9'<Buffer[pos])
        (++pos==Lim)?(f.read(Buffer,Lim),pos = 0):0;
    x = 0;
    while('0'<=Buffer[pos] && Buffer[pos]<='9')
    {
        x = x*10 +Buffer[pos]-'0';
       (++pos==Lim)?(f.read(Buffer,Lim),pos = 0):0;
    }
}
vector <coord> v[50001];
int n,m,d[50001];
const int oo=1073741824;
int main()
{
    register int i,x;
    coord y;
    f.read(Buffer,Lim);
    Read(n);Read(m);
    for (i=1;i<=m;i++)
        {
            Read(x);
            Read(y.nod);
            Read(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 < 50001 > 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;
}