#include <fstream>
#include <vector>
#include <queue>
#define nmax 50005
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
int dmin[nmax],pre[nmax],uz[nmax];
class ComparVf
{
    public:
    bool operator() (const int &x,const int&y)
    {
        return dmin[x]>dmin[y];
    }
};
priority_queue<int,vector<int>,ComparVf> H;
const int INF = 1e9;
int n,m,start;
struct arc
{
    int vf;
    int c;
};
vector <arc> G[nmax];
int lg[nmax];
void citire()
{
    arc aux;
    fin >> n >> m;
    int x,y,c;
    while (fin >> x >> y >> c)
    {
        //adaug pe y in lista de adiacenta a lui x
        /*G[x][lg[x]].vf = y;
        G[x][lg[x]].c = c;
        lg[x]++;*/
        aux.vf = y;
        aux.c = c;
        G[x].push_back(aux);
    }
}
void dijkstra()
{
    int i,j;
    //initializez
    start = 1;
    uz[start] = 1;
    for (i=1;i<=n;i++)
    {
        pre[i] = start;
        dmin[i] = INF;
    }
    dmin[start] = 0;
    pre[start] = 0;
    H.push(start);
    while (!H.empty())
    {
        int vfmin;
        vfmin = H.top();
        H.pop();
        for (i=0;i<G[vfmin].size();i++)
        {
            if (dmin[G[vfmin][i].vf] > dmin[vfmin] + G[vfmin][i].c)
            {
                dmin[G[vfmin][i].vf] = dmin[vfmin] + G[vfmin][i].c;
                H.push(G[vfmin][i].vf);
            }
        }
    }
}
void afisare()
{
    int i;
    for (i=2;i<=n;i++)
        if(dmin[i] == INF)
            fout << "0" << ' ';
        else
            fout << dmin[i] << ' ';
    fout << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);
    citire();
    dijkstra();
    afisare();
    return 0;
}