#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int dim=5e4+10;
const int oo=2e9;
typedef long long ll;
typedef pair<int,int> pi;
int t,T,n,m,a,b,c;

vector < pi > V[dim];
vector < int > d(dim,oo);

struct cmp
{
    bool operator()(int x,int y)
    {
        return (d[x]<d[y]);
    }
};

set < int,cmp > S;
set < int,cmp > ::iterator it;

void Dijkstra()
{
    S.insert(1);
    d[1]=0;
    while(!S.empty())
    {
        int nod=*(S.begin());
        S.erase(S.begin());
        for(pi x:V[nod])
        {
            int vecin=x.first;
            int cost=x.second;
            if(d[vecin]>d[nod]+cost)
            {
                d[vecin]=d[nod]+cost;
                it=S.find(vecin);
                if(it!=S.end())
                    continue;
                else
                    S.insert(vecin);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        V[a].pb({b,c});
    }
    Dijkstra();
    for(int i=2;i<=n;i++)
    if(d[i]==oo) g<<0<<' ';
    else g<<d[i]<<' ';

    return 0;
}