#include <fstream>
#include <vector>
#include <queue>
#include <functional>
#define NMAX 1000
#define INF 999999999
using namespace std;

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

struct varf{int x; int c;
            friend bool operator > (varf,varf);
            };

bool operator>(varf a, varf b)
{
    return a.c>b.c;
}

int n,start;
vector<varf> G[NMAX];
bool uz[NMAX];
int cmin[NMAX];
int prec[NMAX];
priority_queue<varf,vector<varf>,greater<varf> >H;

void citire();
void dijksta();
void afisare();

int main()
{
    citire();
    dijksta();
    afisare();
    return 0;
}
void citire()
{
    varf aux;
    int i,a,m,start=1;
    fin>>n>>m;
    while(fin>>a>>aux.x>>aux.c)
        G[a].push_back(aux);
    uz[start]=1;
    for (i=1;i<=n;i++) {cmin[i]=INF;prec[i]=start;}
    cmin[start]=0; prec[start]=0;
    for (i=0;i<G[start].size();i++)
        {H.push(G[start][i]);
        cmin[G[start][i].x]=G[start][i].c;
        prec[G[start][i].x]=start;
        }
}
void dijksta()
{
    varf aux,alta;
    int nr=1,i;
    while(nr<n && !H.empty())
        {aux=H.top(); H.pop();
        if (!uz[aux.x])
            {uz[aux.x]=1;nr++;
            for (i=0;i<G[aux.x].size();i++)
                {
                if ((cmin[aux.x]+G[aux.x][i].c<cmin[G[aux.x][i].x])&& !uz[G[aux.x][i].x])
                    cmin[G[aux.x][i].x]=cmin[aux.x]+G[aux.x][i].c;
                    prec[G[aux.x][i].x]=aux.x;
                    alta.x=G[aux.x][i].x;
                    alta.c=cmin[G[aux.x][i].x];
                    H.push(alta);
                }
            }
        }
}
void afisare()
{
    int i;
    for (i=1;i<=n;i++)
        if (cmin[i]==INF) fout<<"0"<<" ";
            else
                fout<<cmin[i]<<" ";
}