#include <fstream>
#include <vector>
#define nmax 50001

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n,m;
vector <pair<int,int> > v[nmax];
int viz[nmax];
int d[nmax];

void read()
{
    fin>>n>>m;
    int i,x,y,z;
    for(i=1; i<=m; i++)
       {
           fin>>x>>y>>z;
           v[x].push_back(make_pair(y,z));
       }
    for(i=1; i<=n; i++) d[i]=1e9;
    d[1]=0;
}

void dijkstra()
{
    int i,j;
    for(i=1; i<=n; i++)
        {
            int who=-1, mn=1e9;
            for(j=1; j<=n; j++)
                 if(!viz[j] && d[j]<mn) {mn=d[j]; who=j;}
            int ct=v[who].size();
            for(j=0; j<ct; j++)
                {
                    int dist=v[who][j].second;
                    int nod=v[who][j].first;
                    if(d[nod]>dist+d[who])  d[nod]=d[who]+dist;
                }
            viz[who]=1;
        }
}

int main()
{
    read();
    dijkstra();
    for(int i=2; i<=n; i++) fout<<d[i]<<" ";
    return 0;
}