#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

#define nmax 50001
#define infinite 100000000
int d[nmax];
struct comp
{
    bool operator() (int x,int y)
    {
        return d[x] >d[y];
    }
};
vector < pair <int, int>> a[nmax];
priority_queue <int, vector <int>, comp> coada;

bool viz[nmax];
int nodcurent,vecin,cost,n,m,i,k1,k2,k3,s;

void drum(int s)
{
    coada.push(s);
    viz[s]=1;
    while(coada.empty()==0)
    {
        nodcurent=coada.top();
        coada.pop(); viz[nodcurent]=0;

        for(unsigned int i=0;i<a[nodcurent].size();i++)
        {
            vecin=a[nodcurent][i].first;
            cost=a[nodcurent][i].second;
            if(d[nodcurent]+cost<d[vecin])
            {
                d[vecin]=d[nodcurent]+cost;
                if(viz[vecin]==0)
                {
                    coada.push(vecin);
                    viz[vecin]=1;
                }

            }
        }
    }
    for(i=2;i<=n;i++)
        g<<d[i]<<" ";

}

int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>k1>>k2>>k3;
        a[k1].push_back(make_pair (k2,k3));

    }
    for(i=1;i<=n;i++)
        d[i]=infinite;

    s=1; d[s]=0;
    drum(s);

    return 0;
}