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

struct coord
{
    int cost,nod;
};

typedef pair<int,int> PII;
vector <coord> v[50005];
int n,m,d[50005];
priority_queue<PII>q;
const int oo=1<<30;

inline void Citire()
{
    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);
        }
    fin.close();
}

inline void DIJKSTRA()
{
    int i,len,x,costarico;
    d[1]=0;
    for (i=2;i<=n;i++)
        d[i]=oo;
    q.push(make_pair(1,0));
    while (!q.empty())
        {
            x=q.top().first;
            costarico=q.top().second;
            q.pop();
            if (costarico==d[x])
            {
                len=v[x].size();
                for (i=0;i<len;i++)
                if (d[v[x][i].nod]>d[x]+v[x][i].cost)
                    {
                        d[v[x][i].nod]=d[x]+v[x][i].cost;
                        q.push(make_pair(v[x][i].nod,d[v[x][i].nod]));
                    }
            }
        }
}

inline void Afisare()
{
    int i;
    ofstream fout("dijkstra.out");
    for (i=2;i<=n;i++)
        if (d[i]!=oo)
            fout<<d[i]<<" ";
        else fout<<"0 ";
    fout<<"\n";
    fout.close();
}

int main()
{
    Citire();
    DIJKSTRA();
    Afisare();
    return 0;
}